medium Longest Substring with At Least K Repeating Characters

Problem Statement

Given a string s and an integer k, return the maximum length of the substring where each character appears at least k times. If no such substring exists, return 0.

Examples

Example 1:

• Input: s = "aaabbcc", k = 2
• Output: 7
• Justification: The longest substring is "aaabbcc", where each character ('a', 'b', and 'c') appears at least 2 times.

Example 2:

• Input: s = "ababbc", k = 3
• Output: 0
• Justification: There is no substring exists having each character frequency at least 3.

Example 3:

• Input: s = "abcdef", k = 1
• Output: 6
• Justification: The entire string "abcdef" is the longest substring, as each character appears at least once.

Constraints:

• 1 <= s.length <= 10⁴
• s consists of only lowercase English letters.
• 1 <= k <= 10⁵

Solution

To solve this problem, we will use a divide-and-conquer approach. The idea is to break down the problem into smaller subproblems and solve each recursively. This approach works well because we can split the string at characters that do not meet the frequency requirement and then solve for the resulting substrings.

We start by counting the frequency of each character in the substring. If all characters meet the frequency requirement, we return the length of the substring. If not, we split the string at the first character that doesn't meet the requirement and recursively find the longest valid substring in the left and right parts. The maximum length from these recursive calls gives us the desired result. This approach ensures we examine all possible substrings efficiently.

Step-by-Step Algorithm

1. Initialization:

   • Define a method longestSubstring that takes the string s and integer k as parameters.
   • This method calls a helper function longestSubstringUtil with parameters s, start (0), end (length of s), and k.

2. Helper Function:

   • Inside longestSubstringUtil, check if the length of the substring (end - start) is less than k. If so, return 0 because no substring can have all characters appearing at least k times.

3. Character Frequency Count:

   • Create an array countMap of size 26 to store the frequency of each character in the substring.
   • Iterate through the substring from start to end and update the frequency count for each character in countMap.

4. Identify Splitting Points:

   • Iterate through the substring from start to end. For each character at position mid:
     • If the character frequency in countMap is greater than or equal to k, continue to the next character.
     • If the character frequency is less than k, identify the next position midNext where the character frequency meets the condition.

5. Recursive Calls:

   • Recursively call longestSubstringUtil for the left part of the substring (start to mid) and the right part (midNext to end).
   • Return the maximum length between these two recursive calls.

6. Return Result:

   • If all characters in the substring meet the frequency condition, return the length of the substring (end - start).

Algorithm Walkthrough

Input: s = "aaabbcc", k = 2

1. Initialization:

   • s = "aaabbcc", k = 2
   • Call longestSubstring(s, k) which calls longestSubstringUtil(s, 0, 7, k)

2. Helper Function:

   • start = 0, end = 7
   • Check if end - start < k (7 - 0 < 2). This is false, so continue.

3. Character Frequency Count:

   • Initialize countMap to [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   • Iterate through s from start to end and update countMap:
     • countMap['a' - 'a'] increments to 1, 2, 3 (character positions 0, 1, 2)
     • countMap['b' - 'a'] increments to 1, 2 (character positions 3, 4)
     • countMap['c' - 'a'] increments to 1, 2 (character positions 5, 6)
   • countMap becomes [3, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

4. Identify Splitting Points:

   • Iterate through s from start to end:
     • At mid = 0, 'a' frequency is 3 (>= k), continue.
     • At mid = 1, 'a' frequency is 3 (>= k), continue.
     • At mid = 2, 'a' frequency is 3 (>= k), continue.
     • At mid = 3, 'b' frequency is 2 (>= k), continue.
     • At mid = 4, 'b' frequency is 2 (>= k), continue.
     • At mid = 5, 'c' frequency is 2 (>= k), continue.
     • At mid = 6, 'c' frequency is 2 (>= k), continue.

5. Recursive Calls:

   • All characters meet the frequency condition, so no need for splitting.

6. Return Result:

   • Return the length of the substring: end - start = 7 - 0 = 7

Code

class Solution {

  public int longestSubstring(String s, int k) {
    // Call the utility method with the entire string
    return longestSubstringUtil(s, 0, s.length(), k);
  }

  int longestSubstringUtil(String s, int start, int end, int k) {
    // If the current substring length is less than k, it can't have k repeating characters
    if (end - start < k) return 0;

    // Create a count array to store the frequency of each character
    int[] countMap = new int[26];
    for (int i = start; i < end; i++) {
      countMap[s.charAt(i) - 'a']++;
    }

    // Iterate through the substring
    for (int mid = start; mid < end; mid++) {
      // If the character at mid meets the frequency condition, continue
      if (countMap[s.charAt(mid) - 'a'] >= k) continue;

      // Find the next position where the character frequency is valid
      int midNext = mid + 1;
      while (midNext < end && countMap[s.charAt(midNext) - 'a'] < k) midNext++;

      // Recursively check the left and right parts of the substring
      return Math.max(
        longestSubstringUtil(s, start, mid, k),
        longestSubstringUtil(s, midNext, end, k)
      );
    }

    // All characters meet the frequency condition, return the length of the substring
    return end - start;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    String s1 = "aaabbcc";
    int k1 = 2;
    System.out.println("Example 1:");
    System.out.println("Input: s = \"" + s1 + "\", k = " + k1);
    System.out.println("Output: " + solution.longestSubstring(s1, k1)); // Output: 7

    // Example 2
    String s2 = "ababbc";
    int k2 = 3;
    System.out.println("Example 2:");
    System.out.println("Input: s = \"" + s2 + "\", k = " + k2);
    System.out.println("Output: " + solution.longestSubstring(s2, k2)); // Output: 0

    // Example 3
    String s3 = "abcdef";
    int k3 = 1;
    System.out.println("Example 3:");
    System.out.println("Input: s = \"" + s3 + "\", k = " + k3);
    System.out.println("Output: " + solution.longestSubstring(s3, k3)); // Output: 6
  }
}

Complexity Analysis

Time Complexity

• The time complexity of the algorithm is , where (n) is the length of the string s and (m) is the number of unique characters in the string. The recursion divides the problem into smaller subproblems at each invalid character, leading to multiple recursive calls. In the worst case, this could result in examining all substrings of the string.

Space Complexity

• The space complexity of the algorithm is due to the countMap array, where (m) is the number of unique characters (26 for the English alphabet). Additionally, the recursion stack can go as deep as the length of the string, making the space complexity in the worst case.