SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to find the length of the longest substring where every character appears at least k times. If a character appears fewer than k times, that character splits the string into smaller substrings.

Intuition

We traverse the string and keep track of the frequency of each character. If a character appears fewer than k times, it cannot be part of a valid substring, so we recursively check both halves of the string split at that character.

Approach

1. Count the frequency of each character in the string.
2. Iterate over the string. If a character appears fewer than k times, split the string into two halves and recursively compute the result for each half.
3. The final result is the maximum of the results from the recursive calls or the length of the string if all characters appear at least k times.

Complexity

Time Complexity:

O(n^2) in the worst case due to multiple recursive splits.

Space Complexity:

O(n) for the recursion stack.

Code

C++

class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.empty()) {
            return 0;
        }

        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }

        for (int i = 0; i < s.size(); i++) {
            if (freq[s[i]] < k) {
                int leftPart = longestSubstring(s.substr(0, i), k);
                int rightPart = longestSubstring(s.substr(i + 1), k);
                return max(leftPart, rightPart);
            }
        }

        return s.size();
    }
};

Python

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if not s:
            return 0

        freq = {}
        for c in s:
            freq[c] = freq.get(c, 0) + 1

        for i, c in enumerate(s):
            if freq[c] < k:
                leftPart = self.longestSubstring(s[:i], k)
                rightPart = self.longestSubstring(s[i + 1:], k)
                return max(leftPart, rightPart)

        return len(s)

Java

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < s.length(); i++) {
            if (freq.get(s.charAt(i)) < k) {
                int leftPart = longestSubstring(s.substring(0, i), k);
                int rightPart = longestSubstring(s.substring(i + 1), k);
                return Math.max(leftPart, rightPart);
            }
        }

        return s.length();
    }
}

JavaScript

var longestSubstring = function (s, k) {
    if (!s || !s.length) {
        return 0
    }

    const freq = {}

    for (const c of s) {
        freq[c] = freq[c] + 1 || 1
    }

    for (let i = 0; i < s.length; i++) {
        const c = s[i]

        if (freq[c] < k) {
            return Math.max(
                longestSubstring(s.slice(0, i), k),
                longestSubstring(s.slice(i + 1), k)
            )
        }
    }

    return s.length
};