Leetcode 395 Solution

This article provides solution to leetcode question 395 (longest-substring-with-at-least-k-repeating-characters)
Categories:
Tags:
Access this page by simply typing in "lcs 395" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters

Solution

class Solution {
public:
    int longestSubstring(string s, int k, int l, int r) {
        if (l > r)
            return 0;

        vector<int> a(26);
        for (int i = l; i <= r; i++)
        {
            a[s[i] - 'a']++;
        }

        vector<int> spliters;

        for (int i = l; i <= r; i++)
        {
            if (a[s[i] - 'a'] == 0 || a[s[i] - 'a'] >= k)
                continue;

            spliters.push_back(i);
        }

        if (spliters.size() == 0)
            return r - l + 1;

        spliters.push_back(r + 1);

        int curr = 0;
        int m = 0;

        for (auto it = spliters.begin(); it != spliters.end(); it++)
        {
            int submax = longestSubstring(s, k, curr, *it - 1);
            m = max(m, submax);

            curr = *it + 1;
        }

        return m;
    }

    int longestSubstring(string s, int k) {
        return longestSubstring(s, k, 0, s.size() - 1);
    }
};