В этой задаче LeetCode нам дается строка str и целое число k, и нас просят вернуть самую длинную подстроку str, который состоит только из символов, встречающихся k или более раз.

Другими словами, для строки «aabbbcccc» и значения k, равного 3, самая длинная подстрока, в которой все буквы встречаются 3 или более раз, будет «bbbcccc», поэтому наш ответ будет равен 7.

Решение №1: грубая сила

Самое очевидное решение грубой силы — построить каждую возможную подстроку, а затем проверить, состоит ли она полностью из символов, встречающихся k или более раз. Для этого мы перебираем каждый символ в предоставленной строке, а затем снова зацикливаем с этой точки. На каждой остановке мы проверяем, состоит ли текущая подстрока полностью из символов, встречающихся k или более раз, а затем сохраняем их как самую длинную найденную подстроку, если это действительно так.

В этот код можно внести ряд улучшений производительности, но, в конце концов, он не может конкурировать с более эффективными решениями.

Решение №2: разделяй и властвуй

Для этого подхода мы сначала создаем карту всех букв в str, записывая, сколько раз встречается каждая буква. Затем мы перебираем str, пока не достигнем буквы, которая встречается менее k раз. Поскольку мы знаем, что эта буква не может быть частью ответа, мы можем «разорвать» в этом месте и посмотреть на строку, начинающуюся с предыдущего разрыва и заканчивающуюся этим.

Примечание. Если в строке нет "разрыва", то действительна вся строка.

Умная часть здесь заключается в том, что мы можем снова вызвать ту же функцию, на этот раз передав новую строку, чтобы проверить, является ли она действительной. Это создает рекурсивный вызов, который делит строку вниз и вниз, пока не достигнет точки, где она является самой длинной потенциальной подстрокой.

Например, учитывая строку «aaabcccc» и k, равное 3, мы видим, что строка разорвется, когда достигнет «b». Затем эта функция снова вызовет функцию для «aaa», что допустимо, и поэтому 3 будет возвращено как самая длинная длина подстроки. Затем исходный цикл будет продолжаться до тех пор, пока не достигнет конца строки, после чего он проверит «bbbb», что также допустимо, и вернет 4. Это, конечно, большее из двух чисел, поэтому 4 становится наш ответ.