[JAVA 문제 풀이] 357. Find the Original Typed String II [원본 타이핑 문자열 II 찾기]

Find the Original Typed String II - LeetCode

Can you solve this real interview question? Find the Original Typed String II - Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times. You are given a string word, which represents the final output displayed on Alice's screen. You are also given a positive integer k. Return the total number of possible original strings that Alice might have intended to type, if she was trying to type a string of size at least k. Since the answer may be very large, return it modulo 109 + 7.   Example 1: Input: word = "aabbccdd", k = 7 Output: 5 Explanation: The possible strings are: "aabbccdd", "aabbccd", "aabbcdd", "aabccdd", and "abbccdd". Example 2: Input: word = "aabbccdd", k = 8 Output: 1 Explanation: The only possible string is "aabbccdd". Example 3: Input: word = "aaabbb", k = 3 Output: 8   Constraints: * 1 <= word.length <= 5 * 105 * word consists only of lowercase English letters. * 1 <= k <= 2000

https://leetcode.com/problems/find-the-original-typed-string-ii/description

앨리스는 컴퓨터에 특정 문자열을 입력하려고 시도하고 있습니다.
하지만 그녀는 서투른 경향이 있고 키를 너무 오래 눌러 문자를 여러 번 입력할 수 있습니다.

앨리스 화면에 표시되는 최종 출력을 나타내는 문자열 단어가 주어집니다.
또한 양의 정수 k도 주어집니다.

앨리스가 최소한 k 이상의 크기의 문자열을 입력하려고 했다면,
입력하려고 했을 가능성이 있는 원래 문자열의 총 개수를 반환하세요.

답이 매우 클 수 있으므로 모듈로 10^9 + 7로 반환하세요.

내가 작성한 코드 + 다른 사람의 코

import java.util.*;

class Solution {
    private static final long MOD = (long) 1e9 + 7;

    public int possibleStringCount(String word, int k) {
        List<Integer> list = new ArrayList<>();
        int n = word.length();
        int i = 0;

        // 1. word를 같은 문자가 연속된 블록 단위로 나누어 각 블록의 길이를 저장
        // 예: word = "aabbccdd" → list = [2,2,2,2]
        while (i < n) {
            int j = i + 1;
            while (j < n && word.charAt(j) == word.charAt(j - 1))
                j++;
            list.add(j - i);
            i = j;
        }

        int m = list.size();  // 문자 블록 수

        // 2. 뒤에서부터 가능한 경우 수를 누적 곱으로 저장
        // power[i] = list[i] * list[i+1] * ... * list[m-1] (mod MOD)
        long[] power = new long[m];
        power[m - 1] = list.get(m - 1);
        for (i = m - 2; i >= 0; i--) {
            power[i] = (power[i + 1] * list.get(i)) % MOD;
        }

        // 3. 만약 블록 수 ≥ k → 이미 최소 길이가 k 이상이므로 가능한 조합 모두 유효
        if (m >= k)
            return (int) power[0];  // 모든 블록마다 하나만 고르면 최소 길이 m ≥ k

        // 4. DP 시작: dp[i][j] = i번째 블록부터 고려할 때 추가로 j만큼 길이를 더 채우는 경우의 수
        // 총 길이는 m(블록 개수) + j가 됨 → 이게 k 이상이면 OK
        long[][] dp = new long[m][k - m + 1];

        // 5. 마지막 블록에 대한 초기화
        // j: 남은 추가 길이 (k - m)
        // dp[m-1][j]: 마지막 블록에서 (블록 길이 - 줄여야 하는 양) 만큼 유효
        for (i = 0; i < k - m + 1; i++) {
            if (list.get(m - 1) + i + m > k)
                dp[m - 1][i] = list.get(m - 1) - (k - m - i);
        }

        // 6. 뒤에서부터 DP 계산 (Bottom-up)
        for (i = m - 2; i >= 0; i--) {
            long sum = (dp[i + 1][k - m] * list.get(i)) % MOD;  // j = k - m 에 대한 초기화
            for (int j = k - m; j >= 0; j--) {
                // 누적합 방식으로 dp[i][j] 계산
                sum += dp[i + 1][j];

                // sum에서 범위 초과된 dp 값을 제거
                if (j + list.get(i) > k - m)
                    sum = (sum - dp[i + 1][k - m] + MOD) % MOD;
                else
                    sum = (sum - dp[i + 1][j + list.get(i)] + MOD) % MOD;

                // 현재 블록 길이만큼 곱해서 dp 저장
                dp[i][j] = sum;
            }
        }

        // 최종 결과는 첫 번째 블록부터 시작해서 전체 길이 k를 만드는 경우
        return (int) dp[0][0];
    }
}