Question

395. Longest Substring with At Least K Repeating Characters

中文文档

Description

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.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

 

Constraints:

• 1 <= s.length <= 104
• s consists of only lowercase English letters.
• 1 <= k <= 105

Solutions

Solution 1

class Solution:
  def longestSubstring(self, s: str, k: int) -> int:
    def dfs(l, r):
      cnt = Counter(s[l : r + 1])
      split = next((c for c, v in cnt.items() if v < k), '')
      if not split:
        return r - l + 1
      i = l
      ans = 0
      while i <= r:
        while i <= r and s[i] == split:
          i += 1
        if i >= r:
          break
        j = i
        while j <= r and s[j] != split:
          j += 1
        t = dfs(i, j - 1)
        ans = max(ans, t)
        i = j
      return ans

    return dfs(0, len(s) - 1)

class Solution {
  private String s;
  private int k;

  public int longestSubstring(String s, int k) {
    this.s = s;
    this.k = k;
    return dfs(0, s.length() - 1);
  }

  private int dfs(int l, int r) {
    int[] cnt = new int[26];
    for (int i = l; i <= r; ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    char split = 0;
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] > 0 && cnt[i] < k) {
        split = (char) (i + 'a');
        break;
      }
    }
    if (split == 0) {
      return r - l + 1;
    }
    int i = l;
    int ans = 0;
    while (i <= r) {
      while (i <= r && s.charAt(i) == split) {
        ++i;
      }
      if (i > r) {
        break;
      }
      int j = i;
      while (j <= r && s.charAt(j) != split) {
        ++j;
      }
      int t = dfs(i, j - 1);
      ans = Math.max(ans, t);
      i = j;
    }
    return ans;
  }
}

class Solution {
public:
  int longestSubstring(string s, int k) {
    function<int(int, int)> dfs = [&](int l, int r) -> int {
      int cnt[26] = {0};
      for (int i = l; i <= r; ++i) {
        cnt[s[i] - 'a']++;
      }
      char split = 0;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > 0 && cnt[i] < k) {
          split = 'a' + i;
          break;
        }
      }
      if (split == 0) {
        return r - l + 1;
      }
      int i = l;
      int ans = 0;
      while (i <= r) {
        while (i <= r && s[i] == split) {
          ++i;
        }
        if (i >= r) {
          break;
        }
        int j = i;
        while (j <= r && s[j] != split) {
          ++j;
        }
        int t = dfs(i, j - 1);
        ans = max(ans, t);
        i = j;
      }
      return ans;
    };
    return dfs(0, s.size() - 1);
  }
};

func longestSubstring(s string, k int) int {
  var dfs func(l, r int) int
  dfs = func(l, r int) int {
    cnt := [26]int{}
    for i := l; i <= r; i++ {
      cnt[s[i]-'a']++
    }
    var split byte
    for i, v := range cnt {
      if v > 0 && v < k {
        split = byte(i + 'a')
        break
      }
    }
    if split == 0 {
      return r - l + 1
    }
    i := l
    ans := 0
    for i <= r {
      for i <= r && s[i] == split {
        i++
      }
      if i > r {
        break
      }
      j := i
      for j <= r && s[j] != split {
        j++
      }
      t := dfs(i, j-1)
      ans = max(ans, t)
      i = j
    }
    return ans
  }
  return dfs(0, len(s)-1)
}