DSA Decoded | Day 19: Longest Substring with Atleast K Repeating Characters

Photo by Adrian Siaril on Unsplash

“This is a running series of posts, where I solve DSA problems and try to explain them as thoroughly as possible for anyone to understand. Usually I’ll be using JAVA for solving all problems”

The link to this question is provided below

[embed]Longest Substring with At Least K Repeating Characters - LeetCode Can you solve this real interview question? Longest Substring with At Least K Repeating Characters - Given a string s…leetcode.com

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 greater than or equal to k.

if no such substring exists, return 0.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Constraints:

• 1 <= s.length <= 10^4
• s consists of only lowercase English letters.
• 1 <= k <= 10^5

Intuition:

To find the longest substring with atleast k repeating characters, we have to avoid the characters that are less than k times. That means, those characters wont be a part of the solution string.

We can use those characters as pivot points, and divide the problem into two parts; left and right, and solve them recursively as sub-problems (Divide and Conquer). Ultimately, we would get to a sub-string which has all characters freqeunct atleast k. That would become solution to he subproblem.

For every left and right substring, we compare both results, and return the max length recursively, till we get a global solution.

Even though we slide, we slide to find a range ending with pivot, then this pivot is used to solve the left and right subproblems seperately.

Solution:

class Solution {
    public int longestSubstring(String s, int k) {
        int n=s.length();
        if(n < k) return 0; // if any string is less than k, not possible

        int[] f = new int[26];
        for(int j=0; j<n; j++){
            f[ s.charAt(j) -'a']++;
        }

        int i=0;
        while(i<n){     // find valid pivot
            char c = s.charAt(i);
            if( f[ c-'a' ]!=0 && f[c-'a']<k )
                break;
            i++;
        }

        // never found the pivot, if the current sub problem is valid
        if(i >= n)
            return n;

        // divide into two subproblems,
        // dont solve previous problems, again 
        int left = i==0 ? 0 : longestSubstring(s.substring(0, i), k);
        int right = i==n-1 ? 0 : longestSubstring(s.substring(i+1), k);

        return Math.max(left, right);
    }
}

Complexity:

Time : O(nlogn) , the string is traversed linearly, but recusrion is invlolved.

Space : O(n) , we use counters.