algoadvance

Leetcode 395. Longest Substring with At Least K Repeating Characters Sure, let’s walk through the problem step-by-step.

Problem Statement

Given a string s and an integer k, return 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. What should be returned if there are no substrings meeting the criteria?
    • Return 0 if no such substring exists.
  2. Should the input string be all lowercase?
    • Yes, for simplicity. All characters in s are lowercase English letters.
  3. What is the range of input sizes?
    • The length of s will be in the range [1, 10^4].
    • k will be in the range [1, 10^5].

Strategy

To solve this problem, we could use a recursive divide-and-conquer approach:

  1. Base Case:
    • If the length of the string is less than k, we cannot have any valid substring, so return 0.
  2. Main Idea:
    • For each character that appears less than k times in the string, we know it cannot be part of the wanted substring. Thus, split the string around these characters and apply the same process recursively on the resulting substrings.
  3. Recursive Splitting:
    • Use a frequency map to count occurrences of each character.
    • Split the string at every character that appears fewer times than k.
    • Recursively solve the problem for each segment of the split string.
  4. Combine Results:
    • The answer for the original string is the maximum length obtained from all segments of the split strings.

Code

Here’s the C++ implementation of the described approach:

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

class Solution {
public:
    int longestSubstring(const std::string& s, int k) {
        return longestSubstringHelper(s, 0, s.size(), k);
    }

private:
    int longestSubstringHelper(const std::string& s, int start, int end, int k) {
        if (end - start < k) {
            return 0;
        }

        std::unordered_map<char, int> frequency;
        for (int i = start; i < end; ++i) {
            ++frequency[s[i]];
        }

        for (int mid = start; mid < end; ++mid) {
            if (frequency[s[mid]] < k) {
                int nextMid = mid + 1;
                while (nextMid < end && frequency[s[nextMid]] < k) {
                    ++nextMid;
                }
                return std::max(longestSubstringHelper(s, start, mid, k), 
                                longestSubstringHelper(s, nextMid, end, k));
            }
        }

        return end - start;
    }
};

int main() {
    Solution solution;
    std::string s = "aaabb";
    int k = 3;
    std::cout << "Longest substring length: " << solution.longestSubstring(s, k) << std::endl; // Output: 3 ("aaa")

    s = "ababbc";
    k = 2;
    std::cout << "Longest substring length: " << solution.longestSubstring(s, k) << std::endl; // Output: 5 ("ababb")

    return 0;
}

Time Complexity

This approach balances clarity and efficiency given the problem constraints.

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