Competitive Programing: Vowel Substring

Q: Given a string find all the number of sub-strings which contain all the five vowels at least once.


It is solved in two ways:

1. A slightly more complicated linear scan method
2. By generating all the sub-strings and then checking whether or not it satisfies the our requirements. (brute force)

Code

#include <iostream>
using namespace std;
int vowel[300];  // vowel array
int fi = 0;      // first index
int li = 0;      // last index

// function to check if all the vowel are present
bool checker() {
  if (vowel[int('a')] != 0 && 

      vowel[int('e')] != 0 && 

      vowel[int('i')] != 0 &&
      vowel[int('o')] != 0 &&

      vowel[int('u')] != 0)
    return true;
  return false;
}

int main() {
  int ans = 0;
  string st;
  cin >> st;
  int l = st.length();
  int counter = 0;
  vowel[int(st[0])]++;

  fi = 0;
  li = 0;

  while (li != l - 1) {
    li++;
    ans += counter;

    vowel[int(st[li])]++;
    if (checker()) {
      while (checker()) {
        vowel[int(st[fi])]--;
        counter++;
        fi++;
        ans++;
      }
    }
  }

  cout << "answer according to linear scan=" << ans << endl;

  int ans2 = 0;
  for (int i = 0; i < st.length(); i++)
    for (int j = 1; j <= st.length() - i; j++) {
      string st2 = st.substr(i, j);
      if (st2.find('a') != std::string::npos &&
          st2.find('e') != std::string::npos &&
          st2.find('i') != std::string::npos &&
          st2.find('o') != std::string::npos &&
          st2.find('u') != std::string::npos)
        ans2++;
    }
  cout << "ans according to brute force" << ans2 << endl;

  return 0;
}