Longest Substring with At Least K Repeating Characters

class Solution {
public:
    int findLongestSubstringLength(string str, int k) {
        int letterFrequency[26];
        int maxUniqueLetters = calculateMaxUnique(str);
        int longestLength = 0;
        for (int currentUnique = 1; currentUnique <= maxUniqueLetters; currentUnique++) {
            memset(letterFrequency, 0, sizeof(letterFrequency));
            int left = 0, right = 0, uniqueCount = 0, atLeastKCount = 0;
            while (right < str.length()) {
                if (uniqueCount <= currentUnique) {
                    int index = str[right] - 'a';
                    if (letterFrequency[index] == 0) uniqueCount++;
                    letterFrequency[index]++;
                    if (letterFrequency[index] == k) atLeastKCount++;
                    right++;
                } else {
                    int index = str[left] - 'a';
                    if (letterFrequency[index] == k) atLeastKCount--;
                    letterFrequency[index]--;
                    if (letterFrequency[index] == 0) uniqueCount--;
                    left++;
                }
                if (uniqueCount == currentUnique && uniqueCount == atLeastKCount)
                    longestLength = max(longestLength, right - left);
            }
        }
        return longestLength;
    }

    int calculateMaxUnique(string str) {
        bool exists[26] = {false};
        int uniqueLetterCount = 0;
        for (char c : str) {
            if (!exists[c - 'a']) {
                uniqueLetterCount++;
                exists[c - 'a'] = true;
            }
        }
        return uniqueLetterCount;
    }
};

The provided C++ solution is designed to address the problem of finding the length of the longest substring where each character appears at least k times. The solution involves a combination of techniques including sliding window and frequency counting using arrays.

The core functionality is contained within two methods:

• findLongestSubstringLength which computes the longest valid substring's length,
• calculateMaxUnique which computes the number of unique characters in the input string.

Here’s the breakdown of the method findLongestSubstringLength:

1. Initialize a frequency counter for the letters in the alphabet.
2. Determine the maximum number of unique letters in the string using calculateMaxUnique.
3. Employ a sliding window technique to examine possible substrings, adjusting the window size based on the number of unique characters that need to meet or exceed the frequency k.
4. Use two pointers, left and right, representing the current window's bounds.
5. Count unique characters and characters meeting the minimum frequency as the window expands or contracts.
6. Adjust the longestLength variable whenever the conditions of the current window match the desired criteria (i.e., all unique characters in the window appear at least k times).
7. Return the maximum length found.

The method calculateMaxUnique assists by:

• Tracking which characters have been seen to efficiently count unique characters in the string, which helps in optimizing the sliding window approach based on the actual variety of characters.

This approach ensures that all possible substring configurations are evaluated through dynamic adjustment of window size and character counts, leading to a robust and efficient solution for the problem statement. This dual-method strategy aids in keeping the solution both readable and maintainable while effectively leveraging the sliding window technique complemented by character frequency evaluation.

public class Solution {
    public int findLongestSubstr(String input, int minRepeat) {
        char[] characters = input.toCharArray();
        int[] frequency = new int[26];
        int maxDistinct = calculateMaxDistinctChars(input);
        int maxLen = 0;
        for (int currentDistinct = 1; currentDistinct <= maxDistinct; currentDistinct++) {
            // initialize frequency array
            Arrays.fill(frequency, 0);
            int start = 0, end = 0, index = 0, currentUniqueCount = 0, meetMinRepeatCount = 0;
            while (end < characters.length) {
                // Increase the window size
                if (currentUniqueCount <= currentDistinct) {
                    index = characters[end] - 'a';
                    if (frequency[index] == 0) currentUniqueCount++;
                    frequency[index]++;
                    if (frequency[index] == minRepeat) meetMinRepeatCount++;
                    end++;
                }
                // Decrease the window size
                else {
                    index = characters[start] - 'a';
                    if (frequency[index] == minRepeat) meetMinRepeatCount--;
                    frequency[index]--;
                    if (frequency[index] == 0) currentUniqueCount--;
                    start++;
                }
                if (currentUniqueCount == currentDistinct && currentUniqueCount == meetMinRepeatCount)
                    maxLen = Math.max(end - start, maxLen);
            }
        }

        return maxLen;
    }

    int calculateMaxDistinctChars(String input) {
        boolean[] visited = new boolean[26];
        int maxDistinctChars = 0;
        for (int i = 0; i < input.length(); i++) {
            if (!visited[input.charAt(i) - 'a']) {
                maxDistinctChars++;
                visited[input.charAt(i) - 'a'] = true;
            }
        }
        return maxDistinctChars;
    }
}

The provided Java solution aims to solve the problem of finding the longest substring in a given string where each character appears at least k times. Here's a breakdown of the implementation:

• The findLongestSubstr method is the core method that takes a string and an integer minRepeat as parameters, determining the minimum number of repetitions for each character in the substring.
• A utility method, calculateMaxDistinctChars, counts the maximum number of distinct characters in the string which helps in setting the upper limit for the number of unique characters to consider in different scenarios.
• Within the findLongestSubstr method:
  • An array frequency of size 26 is used to track the frequency of each character within the current window (considering only lowercase English alphabets).
  • The algorithm employs a sliding window technique where start and end define the current window's boundaries.
  • It iteratively adjusts the size of this window to include new characters or exclude some to meet the condition of having exactly currentDistinct unique characters within the window, where each of these characters appears at least minRepeat times.
  • The characters' frequency is incremented or decremented as the window is expanded or contracted. When all characters in the window meet the minimum repeat condition and the number of unique characters matches currentDistinct, it checks if the current window length is the longest found so far.
  • The maximum length of such a window is updated accordingly with each valid window found during the traversal.

The solution efficiently manages the sliding window's size by ensuring the character count within the window always tries to meet the specified conditions, utilizing the array operations to keep track of character counts and performance considerations. Adjustments in the window size are kept minimal to optimize runtime efficiency.