Количество подстрок строки, которая имеет три гласных

Question

Я принимал участие в вызове кодирования на hackerearth, и мне задали следующий вопрос.

Алиса и Боб играют в игру, в которой Боб дает строку SS длиной NN, состоящему из строчных букв английского алфавита к Алисе и попросить ее, чтобы вычислить количество подстроки этой строки, которая содержит ровно три гласные.

Это мой код

import java.io.BufferedReader; 
import java.io.InputStreamReader; 


class TestClass1{ 
public static void main(String args[]) throws Exception { 

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    String line = br.readLine(); 
    int N = Integer.parseInt(line); 


    String stringArray[]=new String[N]; 

    for (int i = 0; i < N; i++) { 
     int len = Integer.parseInt(br.readLine()); 
     stringArray[i]=br.readLine();  
    } 

    for (int i = 0; i < N; i++) { 
     System.out.println(determineNumberOfSubstring(stringArray[i])); 
    } 


} 
public static int determineNumberOfSubstring(String str) 
{ 
    int numberOfSubstring=0; 
    for(int i=0;i<str.length();i++) 
    { 
     int ctr=0; 
     for(int j=1;j<str.length()-i;j++) 
     { 
      String subString = str.substring(i,i+j); 
      if(subString.length()<3) 
      { 
       continue; 
      } 
      if(subString.contains("a")||subString.contains("e")||subString.contains("i")||subString.contains("o")||subString.contains("u") 
       ||subString.contains("A")||subString.contains("E")||subString.contains("I")||subString.contains("O")||subString.contains("U")) 
      { 
       ctr+=3; 
      } 
     } 
     if(ctr==3){ 
      numberOfSubstring++; 
     } 

    } 
    return numberOfSubstring; 
} 

} Иам получение лимит времени превышен в коде выше. Может ли кто-нибудь помочь мне в том, как его оптимизировать.

Update1

Код согласно @GhostCat логике, это должно быть проверено и не окончательный код.

class TestClass1{ 
public static void main(String args[]) throws Exception { 

BufferedReader br = new BufferedReader(new   InputStreamReader(System.in)); 
    String line = br.readLine(); 
    int N = Integer.parseInt(line); 
    String stringArray[]=new String[N]; 

    for (int i = 0; i < N; i++) { 
     int len = Integer.parseInt(br.readLine()); 
     stringArray[i]=br.readLine();  
    } 

    for (int i = 0; i < N; i++) { 
     System.out.println(determineNumberOfSubstring(stringArray[i])); 
    } 
} 
public static int determineNumberOfSubstring(String str) 
{ 
    int numberOfSubstring=0; 
    int ctr=0; 
    int subStringStart=0; 
    Stack<String> s = new Stack<String>(); 
    for(int i=0;i<str.length();i++) 
    { 
     if(isVowel(str.charAt(i))) 
      ctr++; 
     if(ctr==3) 
     { 
      numberOfSubstring++; 
      ctr=0; 
      if(s.empty()) 
       s.push(str.substring(0,i)); 
      else 
       s.push(new String(s.peek().substring(1,i+1))); 
      i=str.indexOf(s.peek().charAt(1))-1; 
     } 
    } 
    return numberOfSubstring; 
} 
private static boolean isVowel(char c) { 
    if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u' 
      ||c=='A'||c=='E'||c=='I'||c=='O'||c=='U') 
     return true; 
    return false; 
} 

}

Answer 1

Подсказка: ваш код итерация всей подстроки для каждого и любого нижнего и верхнего случая гласного есть. И это происходит в цикле в цикле.

Вместо этого: используйте ОДИН цикл, который пропускает символы входной строки. И затем проверяйте каждую позицию, если она является гласной, проверяя набор символов (содержащий эти действительные гласные). Последнее, что вам нужно: простое «скользящее» окно; например: когда вы обнаружите три гласных, вы можете увеличить счетчик; затем «забыть» о первом из трех гласных, которые вы только что нашли; как в:

a x e y i --> vowels a/e/i give one substring 
    x e y i ... and you look out for the next substring e/i/... now 

Фактическая реализация остаются в качестве упражнения для читателя ...

Короче говоря: этот счет может быть вычислен путем обработки ввода РАЗ. Ваш код повторяется несколько раз более одного раза. Ну, не бесчисленное количество, но N * N * еще немного.

(одна вещь, чтобы быть осторожным с: при использовании Set<Character> быть точным, когда вы поворачиваете значение char в Character объекта, вы хотите, чтобы свести к минимуму случаи, что происходит, тоже, так как это довольно дорогая операция)