Количество действительных подстроков ⇐ JAVA

[Anonymous]

Учитывая входная строка, содержит буквы от 'a' to 'g' < /p>
count, сколько подстроков существует во входной строке, такая, что
частота любого символа внутри подстроения не больше, чем
abaa, присутствующая в подстроении. /> Объяснение: Допустимые комбинации: < /p>
a b a a ab ba ba aba baa. Сайт, но обнаружил, что я не могу редактировать свой пост, поэтому добавив его здесь снова. вывод. < /p>

Код: Выделить всё

public class Main {
public static int solve(String str) {
int n = str.length();
int[] freq = new int[7]; // Frequency array for 'a' to 'g'
int left = 0, right = 0, distinct = 0, count = 0;

while (right < n) {
int rightChar = str.charAt(right) - 'a';
if (freq[rightChar] == 0) distinct++; // New character in window
freq[rightChar]++;

// Ensure all character frequencies  distinct) {
int leftChar = str.charAt(left) - 'a';
freq[leftChar]--;
if (freq[leftChar] == 0) distinct--; // Removed a distinct character
left++;
}

// Count valid substrings ending at `right`
//System.out.println(left+":"+right);
//count += (right - left + 1);
right++;
}

return count;
}

public static void main(String[] args) {
System.out.println(solve("abaa"));  // Output: 8
System.out.println(solve("abab"));  // Output: 10
System.out.println(solve("aacd"));  // Output: 9

}

}

I имеет еще одну идею о создании всех возможных подстроков, а также использует Hashmap, который хранит частоту каждого символа, а затем, а затем, являются ли они действительными или нет, которые требуют o (n n k), где n -размер n string, k - это число, поддерживаемые SLAHMAP. Подход с оконным окном, но понял, что это не правильный способ решить проблему.>

Подробнее здесь: https://stackoverflow.com/questions/795 ... substrings