Check all occurrences of a letter appear before another letter C++

Question

I have a string S consisting of N letters 'a' or 'b'. This should return true when all occurrences of 'a' are before all occurrences of 'b' and return false otherwise.

b does not need to occur in S and a does not need to occur in S

For example

S='aabbb' returns true 
S = 'ba' returns false
S = 'aaa' returns true
S= 'b' returns true
S='abba' returns false

this is my solution but it displays 1 extra true. I don't know why.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector <string> vec;
    int n;
    string item;
    int contora=0,contorb=0;
    cout<<"n: ";
    cin>>n;
    cout << "Enter a string: ";
    for(int i=0;i<= n;i++){
       getline(cin, item);
       //cin>>item;
     vec.push_back(item);
     }
        
    for (int j=0; j <= n; j++) {
            cout << vec[j];
    }
   cout<<endl;

    for (auto of:vec) {
        if (of.find("ba") != std::string::npos)
            cout << "false";
            else 
            cout<<"true";
    }
  
    return 0;
}

Answer 1

Adding some debug output to the code shows a couple of issues:

1. The first for loop reads in n+1 strings, while we are expecting the user to enter only n strings. The second for loop also prints n+1 strings, although that's not a problem, because the vector contains n+1 elements.
2. Due to mixing both std::cin >> and std::getline for reading user input, the first string read with std::getline is empty. You would need whether to:
   • use std::getline for all the user input readings (and, for n, convert the string to a number), or
   • flush the input buffer with cin.ignore after the std::cin >>, as explained in this answer.

The code below fixes those two issues and adds some debug output (it also follows a few best practices such as, not using namespace std;, defining variables next to their first use, value-initializing local variables, and using block braces even for one-line blocks).

[Demo]

#include <iostream>  // cin, cout
#include <limits>
#include <string>  // getline
#include <vector>

int main() {
    int n{};
    std::cout << "n: ";
    std::cin >> n;
    std::cout << n << "\n\n";
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

    std::vector<std::string> vec{};
    for (int i = 0; i < n; i++) {
        std::cout << "Enter a string: ";
        std::string item{};
        std::getline(std::cin, item);
        std::cout << "item: " << i << ": '" << item << "'\n";
        vec.push_back(item);
    }
    std::cout << "\n";

    for (auto& of : vec) {
        std::cout << "'" << of << "': ";
        if (of.find("ba") != std::string::npos) {
            std::cout << "false\n";
        } else {
            std::cout << "true\n";
        }
    }
}

// Outputs:
//
//   n: 5
//
//   Enter a string: item: 0: 'aabbb'
//   Enter a string: item: 1: 'ba'
//   Enter a string: item: 2: 'aaa'
//   Enter a string: item: 3: 'b'
//   Enter a string: item: 4: 'abba'
//
//   'aabbb': true
//   'ba': false
//   'aaa': true
//   'b': true
//   'abba': false

---

For this particular case, you could also use std::is_partitioned. This algorithm tells you if all the elements of a range that satisfy a given predicate appear before all the elements that don't (see here). The predicate would check if a character is equal to 'a'.

[Demo]

#include <algorithm>  // is_partitioned
#include <cstring>  // strlen
#include <fmt/core.h>

int main() {
    for (auto&& s : { "aabbb", "ba", "aaa", "b", "abba" }) {
        fmt::print("'{}': {}\n", s, std::is_partitioned(s, s + strlen(s),
            [](unsigned char c) { return c == 'a'; }));
    }
}

Answer 2

Wording it differently, you're trying to check if there are any characters in the string that come after a. If the answer is no, your function will return true, and false otherwise.

bool HasCorrectOrder(char prefix_char, char suffix_char, std::string_view str) {
  if (str.empty()) {
    return true;
  }
  // Run through all the preceeding characters.
  int index = 0;
  while (str[index] == prefix_char && index < str.size()) {
    ++index;
  }
  // At this point, if we've reached the end of the string, that means there are
  // no characters after the preceeding character. So we can return true.
  if (index == str.size()) {
    return true;
  }
  // As there are more characters left, they should all be equal to the
  // suffix_char in order for the ordering to be correct.
  while (str[index] == suffix_char && index < str.size()) {
    ++index;
  }
  return (index == str.size());
}

Running a quick check:

void RunTest() {
  std::vector<std::string> test_strings = {"aabbb", "ba", "aaa", "b", "abba"};
  for (std::string_view str : test_strings) {
    std::cout << "S = " << str << " returns "
              << (HasCorrectOrder(/*prefix_char=*/'a',
                                  /*suffix_char=*/'b', str) ? "true" : "false")
              << std::endl;
  }
}

returns:

S = aabbb returns true
S = ba returns false
S = aaa returns true
S = b returns true
S = abba returns false

Answer 3

After fixing the loop logic, here is another simple solution you could use, with the is_sorted algorithm:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    // ...

    for (auto of : vec)
        std::cout << std::boolalpha << std::ranges::is_sorted(of);
}

This compiles with C++20 support, and it works because strings are ranges of characters, for which an operator< is defined. It happens to be the case that 'a' < 'b', so this simple expression is all you need.

Answer 4

You just need to find "ba" occurrences. C++ string type already provides such function. Complexity is linear on string length O(n)

#include <iostream>
#include <string>

void checker(const std::string S) 
{
    if (S.find("ba") != std::string::npos) {
        std::cout << "false" << '\n';
    } else {
        std::cout << "true" << '\n';
    }
}