algoadvance

Leetcode 395. Longest Substring with At Least K Repeating Characters

Problem Statement

Given a string s and an integer k, you need to find the length of the longest substring of s such that the frequency of each character in this substring is at least k.

Clarifying Questions

  1. Input Constraints:
    • Is the input string always composed of lowercase English letters?
    • What is the maximum length of the string s?
  2. Output Requirements:
    • Should the function return the length of the longest valid substring?
  3. Edge Cases:
    • What should be returned if s is an empty string or if k is greater than the length of s?

Assumptions

  1. The input string s consists of lowercase English letters.
  2. The length of string s can be up to 10^4.
  3. If s is empty or k is greater than the length of s, return 0.

Strategy

A divide and conquer approach can be effective for solving this problem since the longest valid substring must also satisfy the same property in each divided part of the string. Here’s the plan:

  1. Base Case:
    • If the length of s is less than k, no substring can satisfy the condition. Return 0.
  2. Recursive Case:
    • Count the frequency of each character in s.
    • Use a pivot point where we split the string. The pivot is any character that appears less than k times because any substring containing this character can’t satisfy the requirement.
    • Recursively apply the same logic to the substrings obtained by splitting s at this pivot.
  3. Combining Results:
    • The result for the current string s will be the max length of valid substrings found from the recursive calls.

Code

public class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        return longestSubstringHelper(s, k, 0, s.length());
    }
    
    private int longestSubstringHelper(String s, int k, int start, int end) {
        if (end - start < k) {
            return 0;
        }

        int[] freq = new int[26];
        for (int i = start; i < end; i++) {
            freq[s.charAt(i) - 'a']++;
        }

        for (int i = start; i < end; i++) {
            if (freq[s.charAt(i) - 'a'] < k) {
                int leftSubstring = longestSubstringHelper(s, k, start, i);
                int rightSubstring = longestSubstringHelper(s, k, i + 1, end);
                return Math.max(leftSubstring, rightSubstring);
            }
        }

        return end - start;
    }
}

Time Complexity

This approach provides a balance between efficiency and simplicity, adequately solving the problem for allowed constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI