LeetCode 2020-11-26: Longest Substring with At Least K ...

Longest Substring with At Least K Repeating Characters (medium) の挑戦メモです。

問題の概要

• 与えられた文字列から得られる部分文字列の中で、その部分文字列に含まれる各種文字がそれぞれ k 回以上現れる条件を満たす最大の部分文字列 (の長さ) を求める

考え方

• こんな感じで再帰処理すればよいのでは？
  1. 注目している (部分) 文字列において、それぞれの文字が何文字出現しているかを数え上げる
  2. 各種文字がいずれも k 文字以上出現していれば、その文字列の長さを返す
  3. k 文字未満の出現回数の文字が現れる場所で文字列を分割する
  4. 分割されたそれぞれの部分文字列について再帰的に 1. から処理し、得られた戻り値のうち最大の値を返す
• 実装 → submit → 一回 wrong answer 💦 → accept
  • Runtime 1ms で Your runtime beats 77.47 % of java submissions. 🤔
• あと 1ms を削るために色々試して 0ms 達成 🎉

コード

class Solution {
    public int longestSubstring(String s, int k) {
        // 毎回 - 'a' して 0~25 の数値に変換するのが無駄に感じられるので、事前に 0~25 の数値に変換しておく
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            chars[i] -= 'a';
        }

        return findLongestSubstringLen(chars, 0, s.length(), k, new int[26]);
    }

    int findLongestSubstringLen(char[] chars, int beginIndex, int endIndex, int k, int[] freq) {
        if (endIndex - beginIndex < k) {
            return 0;
        }

        Arrays.fill(freq, 0);
        for (int i = beginIndex; i < endIndex; i++) {
            freq[chars[i]]++;
        }

        // 1 回以上 k 回未満の出現回数である文字を把握しておく
	// どの文字が対象となるのかをビットで表現する
        int skipFlags = 0;
        for (int i = 25; i >= 0; i--) {
            skipFlags = (skipFlags << 1) | ((freq[i] > 0 && freq[i] < k) ? 1 : 0);
        }

        if (skipFlags == 0) {
            return endIndex - beginIndex;
        }

        int result = 0;
        int last = beginIndex;
        for (int i = beginIndex; i < endIndex; i++) {
            if (((skipFlags >> (chars[i])) & 1) == 1) {
	        // これまでに見つかった最長の部分文字列よりも長い部分文字列のみ、再帰処理をする
                if (i - last > result) {
                    result = Math.max(findLongestSubstringLen(chars, last, i, k, freq), result);
                }
                last = i + 1;
            }
        }

        if (endIndex - last > result) {
            result = Math.max(findLongestSubstringLen(chars, last, endIndex, k, freq), result);
        }

        return result;
    }
}