月度归档： 2025 年 7 月

3304.找出第K个字符I

目标

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k。

现在 Bob 会要求 Alice 执行以下操作 无限次 :

  • 将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。

例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行足够多的操作后， word 中 至少 存在 k 个字符，此时返回 word 中第 k 个字符的值。

注意，在操作中字符 'z' 可以变成 'a'。

示例 1:

输入：k = 5
输出："b"
解释：
最初，word = "a"。需要进行三次操作:
生成的字符串是 "b"，word 变为 "ab"。
生成的字符串是 "bc"，word 变为 "abbc"。
生成的字符串是 "bccd"，word 变为 "abbcbccd"。

示例 2:

输入：k = 10
输出："c"

说明：

  • 1 <= k <= 500

思路

开始的时候有一个字符 a，可以反复执行以下操作：将现有的所有字母替换为它在字母表中的下一个字母（z 的下一个字母为 a），拼接到当前字符后面。返回第 k 个字母。

暴力模拟操作过程。

代码


/**
 * @date 2025-07-03 8:48
 */
public class KthCharacter3304 {

    public char kthCharacter(int k) {
        StringBuilder sb = new StringBuilder();
        sb.append('a');
        while (sb.length() < k) {
            String s = sb.toString();
            int length = s.length();
            for (int i = 0; i < length; i++) {
                char c = (char) ('a' + (s.charAt(i) - 'a' + 1) % 26);
                sb.append(c);
            }
        }
        return sb.toString().charAt(k - 1);
    }

}

性能

3333.找到初始输入字符串II

目标

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。

给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。同时给你一个 正 整数 k ，表示一开始 Alice 输入字符串的长度 至少 为 k 。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

输入：word = "aabbccdd", k = 7
输出：5
解释：
可能的字符串包括："aabbccdd" ，"aabbccd" ，"aabbcdd" ，"aabccdd" 和 "abbccdd" 。

示例 2：

输入：word = "aabbccdd", k = 8
输出：1
解释：
唯一可能的字符串是 "aabbccdd" 。

示例 3：

输入：word = "aaabbb", k = 3
输出：8

说明：

  • 1 <= word.length <= 5 * 10^5
  • word 只包含小写英文字母。
  • 1 <= k <= 2000

思路

有一个字符串，其中可能存在字符由于按键失灵没有及时抬起，导致该字符被输入多次。求原始字符串的总方案数，已知原字符串长度至少为 k。

与 3330.找到初始输入字符串I 相比取消了至多一个错误的限制，增加了原始字符的长度限制。

// todo

代码

性能

3330.找到初始输入字符串I

目标

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。

尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。

给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

示例 1：

输入：word = "abbcccc"
输出：5
解释：
可能的字符串包括："abbcccc" ，"abbccc" ，"abbcc" ，"abbc" 和 "abcccc" 。

示例 2：

输入：word = "abcd"
输出：1
解释：
唯一可能的字符串是 "abcd" 。

示例 3：

输入：word = "aaaa"
输出：4

提示：

  • 1 <= word.length <= 100
  • word 只包含小写英文字母。

思路

有一个字符串，其中可能存在至多一个字符由于按键失灵没有及时抬起，导致该字符被输入多次。求原始字符串的总方案数。

找到相邻的重复字符，假设重复了 k 次，那么就有 k 种可能（即多输入了 0 次、1 次、……、k - 1 次）。假设总共有 l 个相邻重复字符，需要减去 l - 1，因为多录入 0 次被重复计数了。

代码


/**
 * @date 2025-07-01 9:01
 */
public class PossibleStringCount3330 {

    public int possibleStringCount(String word) {
        int res = 0;
        int n = word.length();
        int l = 0, r = 0, cnt = 0;
        while (r < n) {
            while (r < n && word.charAt(r) == word.charAt(l)) {
                r++;
            }
            int p = r - l;
            cnt += p == 0 ? 0 : 1;
            res += p;
            l = r;
        }
        return res - cnt + 1;
    }

}

性能