LeetCode 395.少なくともK個の繰り返し文字を含む最長の部分文字列（スライドウィンドウ）

Leetcode 395 Longest Substring With Least K Repeating Characters Sliding Window

中

T内のすべての文字がk回以上表示されるように、特定の文字列（小文字のみで構成される）の最長の部分文字列Tの長さを見つけます。

例1：
入力：
s =“ aaabb”、k = 3
出力：
3
「a」が3回繰り返されるため、最長の部分文字列は「aaa」です。

例2：
入力：
s =“ ababbc”、k = 2
出力：
5
「a」が2回繰り返され、「b」が3回繰り返されるため、最長の部分文字列は「ababb」です。

問題の意味

文字列sと最大部分文字列の正の整数kが与えられた場合、すべての文字sの最小値がk回出現するようにsを見つけ、部分文字列の最大長を見つけます

考え

スライドウィンドウ。最大26の可能な文字、1〜26 wのトラバーサル、部分文字列の出現数に含まれるwの異なる考慮事項の部分文字列の文字数異なる文字によるスライディングウィンドウの要求w> = kのサブ最大文字列長

コード

class Solution { public int longestSubstring(String s, int k) { int n = s.length(), i = 0, j = 0, ans = 0, uniques = 0, w = 0, numK = 0, idx = 0 // w: number of distinct character considered // numK: number of characters appearing more than k times in the window // uniques: number of distinct characters in the window int[] cnt = new int[26] for (w = 1 w <= 26 ++w) { i = 0 j = 0 uniques = 0 numK = 0 Arrays.fill(cnt, 0) while (j < n && i <= j) { if (uniques <= w) { idx = s.charAt(j++) - 'a' if (cnt[idx] == 0) { ++uniques } ++cnt[idx] if (cnt[idx] == k) { ++numK } } else { idx = s.charAt(i++) - 'a' if (cnt[idx] == k) { --numK } --cnt[idx] if (cnt[idx] == 0) { --uniques } } if (uniques == w && uniques == numK) { ans = Math.max(j - i, ans) } } } return ans } }