2840.判断通过操作能否让字符串相等II

目标

给你两个字符串 s1 和 s2 ,两个字符串长度都为 n ,且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次:

选择两个下标 i 和 j ,满足 i < j 且 j - i 是 偶数,然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等,那么返回 true ,否则返回 false 。

示例 1:

输入:s1 = "abcdba", s2 = "cabdab"
输出:true
解释:我们可以对 s1 执行以下操作:
- 选择下标 i = 0 ,j = 2 ,得到字符串 s1 = "cbadba" 。
- 选择下标 i = 2 ,j = 4 ,得到字符串 s1 = "cbbdaa" 。
- 选择下标 i = 1 ,j = 5 ,得到字符串 s1 = "cabdab" = s2 。

示例 2:

输入:s1 = "abe", s2 = "bea"
输出:false
解释:无法让两个字符串相等。

说明:

  • n == s1.length == s2.length
  • 1 <= n <= 10^5
  • s1 和 s2 只包含小写英文字母。

思路

有两个长度为 n 的字符串 s1 和 s2,判断能否通过操作使二者相等,每次操作交换下标之差为偶数的字母。

2839.判断通过操作能否让字符串相等I 相比,字符串长度由 4 变成了 n,操作的下标之差由 2 变成了偶数。

由于本身使用的就是一般解法,没有去特判具体的下标,可以复用之前的代码。

将字母根据下标分组,

代码


/**
 * @date 2026-03-30 15:41
 */
public class CheckStrings2840 {

    public boolean checkStrings(String s1, String s2) {
        int[][] chars = new int[2][26];
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            chars[i % 2][s1.charAt(i) - 'a']++;
            chars[i % 2][s2.charAt(i) - 'a']--;
        }
        for (int[] ca : chars) {
            for (int c : ca) {
                if (c != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

性能

2839.判断通过操作能否让字符串相等I

目标

给你两个字符串 s1 和 s2 ,两个字符串的长度都为 4 ,且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次:

  • 选择两个下标 i 和 j 且满足 j - i = 2 ,然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等,那么返回 true ,否则返回 false 。

示例 1:

输入:s1 = "abcd", s2 = "cdab"
输出:true
解释: 我们可以对 s1 执行以下操作:
- 选择下标 i = 0 ,j = 2 ,得到字符串 s1 = "cbad" 。
- 选择下标 i = 1 ,j = 3 ,得到字符串 s1 = "cdab" = s2 。

示例 2:

输入:s1 = "abcd", s2 = "dacb"
输出:false
解释:无法让两个字符串相等。

说明:

  • s1.length == s2.length == 4
  • s1 和 s2 只包含小写英文字母。

思路

有两个长度为 4 的字符串 s1 和 s2,判断能否通过操作使二者相等,每次操作可将第一个与第三个 或者 第二个与第四个 字母交换。

实际上就是判断 s1[0]s1[2] 与 s2[0]s2[2] 或者 s2[2]s2[0] ,以及 s1[1]s1[3] 与 s2[1]s2[3] 或者 s2[3]s2[1] 是否相等。

为了避免复杂判断,直接根据奇偶性分组,s1 中的字母 +1s2 中的字母 -1,最后判断字母出现次数是否为 0 即可。

代码


/**
 * @date 2026-03-29 16:28
 */
public class CanBeEqual2839 {

    public boolean canBeEqual(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Map<Character, Integer>[] map = new HashMap[2];
        Arrays.setAll(map, x -> new HashMap<>());
        for (int i = 0; i < 4; i++) {
            int rem = i % 2;
            map[rem].merge(chars1[i], 1, Integer::sum);
            map[rem].merge(chars2[i], -1, Integer::sum);
        }
        for (int i = 0; i < 2; i++) {
            for (Integer value : map[i].values()) {
                if (value != 0) {
                    return false;
                }
            }
        }
        return true;
    }

}

性能

1415.长度为n的开心字符串中字典序第k小的字符串

目标

一个 「开心字符串」定义为:

  • 仅包含小写字母 ['a', 'b', 'c'].
  • 对所有在 1 到 s.length - 1 之间的 i ,满足 s[i] != s[i + 1] (字符串的下标从 1 开始)。

比方说,字符串 "abc","ac","b" 和 "abcbabcbcb" 都是开心字符串,但是 "aa","baa" 和 "ababbc" 都不是开心字符串。

给你两个整数 n 和 k ,你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串,如果长度为 n 的开心字符串少于 k 个,那么请你返回 空字符串 。

示例 1:

输入:n = 1, k = 3
输出:"c"
解释:列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

示例 2:

输入:n = 1, k = 4
输出:""
解释:长度为 1 的开心字符串只有 3 个。

示例 3:

输入:n = 3, k = 9
输出:"cab"
解释:长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

示例 4:

输入:n = 2, k = 7
输出:""

示例 5:

输入:n = 10, k = 100
输出:"abacbabacb"

说明:

  • 1 <= n <= 10
  • 1 <= k <= 100

思路

使用小写字母 a b c 构造相邻不重复的长度为 n 的字符串,求字典序第 k 小的字符串。

按顺序回溯构造长度为 n 的字符串,直到第 k 个结束返回。

代码


/**
 * @date 2026-03-16 13:55
 */
public class GetHappyString1415 {

    private char[] curChar = new char[]{'a', 'b', 'c'};

    public String getHappyString(int n, int k) {
        List<String> list = new ArrayList<>(k);
        char[] chars = new char[n];
        dfs(n, k, '-', 0, chars, list);
        return list.size() < k ? "" : list.get(k - 1);
    }

    public void dfs(int n, int k, char prev, int l, char[] chars, List<String> list) {
        if (list.size() == k) {
            return;
        }
        if (l == n) {
            list.add(new String(chars));
            return;
        }
        for (char c : curChar) {
            if (c == prev) {
                continue;
            }
            chars[l] = c;
            dfs(n, k, c, l + 1, chars, list);
        }
    }

}

性能

1888.使二进制字符串字符交替的最少反转次数

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次:

  • 类型 1 :删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
  • 类型 2 :选择 字符串 s 中任意一个字符并将该字符 反转 ,也就是如果值为 '0' ,则反转得到 '1' ,反之亦然。

请你返回使 s 变成 交替 字符串的前提下, 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的,需要满足任意相邻字符都不同。

  • 比方说,字符串 "010" 和 "1010" 都是交替的,但是字符串 "0100" 不是。

示例 1:

输入:s = "111000"
输出:2
解释:执行第一种操作两次,得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作,得到 s = "101010" 。

示例 2:

输入:s = "010"
输出:0
解释:字符串已经是交替的。

示例 3:

输入:s = "1110"
输出:1
解释:对第二个字符执行第二种操作,得到 s = "1010" 。

说明:

  • 1 <= s.length <= 10^5
  • s[i] 要么是 '0' ,要么是 '1' 。

思路

有一个二进制字符串 s,每次操作:1.可以将首字母移动到末尾;2.或者将任意字符反转,求将 s 变为交替字符串所需的最小反转次数,即最少的操作 2 次数。

由于不考虑首尾移动的次数,可以将首尾相接,考虑字符串 s + s。交替字符串就两种,可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101...,假设所需的反转次数为 k,那么 10101010... 所需的反转次数为 n - k,参考 1758.生成交替二进制字符串的最少操作数

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时,如果下标的奇偶性与元素值的奇偶性不同,说明差异个数减一。移入窗口同理,操作次数加一。

代码


/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            // 如果长度为偶数,操作1不会改变下标的奇偶性,比如 i,i + n 的奇偶性相同,后面循环中 ops 并不会发生变化
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

1784.检查二进制字符串字段

目标

给你一个二进制字符串 s ,该字符串 不含前导零 。

如果 s 包含 零个或一个由连续的 '1' 组成的字段 ,返回 true​​​ 。否则,返回 false 。

示例 1:

输入:s = "1001"
输出:false
解释:由连续若干个 '1' 组成的字段数量为 2,返回 false

示例 2:

输入:s = "110"
输出:true

说明:

  • 1 <= s.length <= 100
  • s[i] 为 '0' 或 '1'
  • s[0] 为 '1'

思路

有一个 不含前导零 的二进制字符串,判断除了开头连续的 1 之外还有没有其它的 1

即判断是否存在 01 子串。

代码


/**
 * @date 2026-03-06 8:46
 */
public class CheckOnesSegment1784 {

    public boolean checkOnesSegment_v1(String s) {
        return s.indexOf("01") == -1;
    }

}

性能

1545.找出第N个二进制字符串中的第K位

目标

给你两个正整数 n 和 k,二进制字符串 Sn 的形成规则如下:

  • S1 = "0"
  • 当 i > 1 时,Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串联操作,reverse(x) 返回反转 x 后得到的字符串,而 invert(x) 则会翻转 x 中的每一位(0 变为 1,而 1 变为 0)。

例如,符合上述描述的序列的前 4 个字符串依次是:

  • S1 = "0"
  • S2 = "011"
  • S3 = "0111001"
  • S4 = "011100110110001"

请你返回 Sn 的 第 k 位字符 ,题目数据保证 k 一定在 Sn 长度范围以内。

示例 1:

输入:n = 3, k = 1
输出:"0"
解释:S3 为 "0111001",其第 1 位为 "0" 。

示例 2:

输入:n = 4, k = 11
输出:"1"
解释:S4 为 "011100110110001",其第 11 位为 "1" 。

示例 3:

输入:n = 1, k = 1
输出:"0"

示例 4:

输入:n = 2, k = 3
输出:"1"

说明:

  • 1 <= n <= 20
  • 1 <= k <= 2^n - 1

思路

长度为 n 的二进制字符串的递推公式为 S_1 = 0, S_i = S_(i-1) + "1" + reverse(invert(S_(i-1))),返回 S_n 的 第 k 位 字符,k1 开始。

简单的做法是根据题意模拟,改写一下递推公式的下标,从 i = 0 开始,已知递推公式 s[0] = '0', s[i] = s[i - 1] + '1' + invertAndReverse(s[i - 1]),求 s[n - 1].charAt(k - 1)

一个更优的做法是递归。s[i] 的长度 len[i] = 2 * len[i - 1] + 1 => len[i] + 1 = 2 (len[i - 1] + 1)len[i] + 1 是一个首项为 2,公比为 2 的等比数列,第 i 项长度为 2^i - 1。可以将它划分成三部分,注意这里下标从 1 开始:

  • 1 ~ 2^(i - 1) - 1s[i - 1],如果 k 在左半边,问题变为 s[i - 1] 的第 k 个字符
  • 2^(i - 1) 值是 1,直接返回
  • 2^(i - 1) + 1 ~ 2^i - 1invertAndReverse(s[i - 1]),如果 k 在右半边,问题变为 invertAndReverse(s[i - 1]) 的第 k - 2^(i - 1) 个字符,也是 invert(s[i - 1]) 的第 2^(i - 1) - k + 2^(i - 1) = 2^i - k 个字符。

代码


/**
 * @date 2026-03-03 14:13
 */
public class FindKthBit1545 {

    public char findKthBit(int n, int k) {
        StringBuilder[] s = new StringBuilder[n];
        Arrays.setAll(s, x -> new StringBuilder());
        s[0].append('0');
        for (int i = 1; i < n; i++) {
            s[i].append(s[i - 1]).append('1').append(invertAndReverse(s[i - 1]));
        }
        return s[n - 1].charAt(k - 1);
    }

    public StringBuilder invertAndReverse(StringBuilder origin) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < origin.length(); i++) {
            if (origin.charAt(i) == '0') {
                res.append('1');
            } else {
                res.append('0');
            }
        }
        return res.reverse();
    }

}

性能

761.特殊的二进制字符串

目标

特殊的二进制字符串 是具有以下两个性质的二进制序列:

  • 0 的数量与 1 的数量相等。
  • 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制字符串 s。

一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串,并交换它们。两个字符串是连续的,如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1。

返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" (在 s[1] 出现) 和 "1100" (在 s[3] 出现)进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

示例 2:

输入:s = "10"
输出:"10"

说明:

  • 1 <= s.length <= 50
  • s[i] 为 '0' 或 '1'。
  • s 是一个特殊的二进制字符串。

思路

代码

性能

696.计数二进制子串

目标

给定一个字符串 s,统计并返回具有相同数量 0 和 1 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现(不同位置)的子串也要统计它们出现的次数。

示例 1:

输入:s = "00110011"
输出:6
解释:6 个子串满足具有相同数量的连续 1 和 0 :"0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意,一些重复出现的子串(不同位置)要统计它们出现的次数。
另外,"00110011" 不是有效的子串,因为所有的 0(还有 1 )没有组合在一起。

示例 2:

输入:s = "10101"
输出:4
解释:有 4 个子串:"10"、"01"、"10"、"01" ,具有相同数量的连续 1 和 0 。

说明:

  • 1 <= s.length <= 10^5
  • s[i] 为 '0' 或 '1'

思路

统计二进制字符串 s 中满足条件的子串个数。子串需满足 01 的个数相等,且子串中所有 0 都是相邻且连续的(由于数量相同,子串中所有的 1 也是相邻且连续的),即 01 都是成组连续的。

00011 满足条件的子串个数为 min(3, 2),可以分组循环字符串,记录前一组的个数,累加二者最小值即可。

代码


/**
 * @date 2026-02-24 16:14
 */
public class CountBinarySubstrings696 {

    public int countBinarySubstrings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int preCnt = 0;
        int i = 0;
        int res = 0;
        while (i < n) {
            int start = i;
            while (i < n && chars[start] == chars[i]) {
                i++;
            }
            int cnt = i - start;
            res += Math.min(preCnt, cnt);
            preCnt = cnt;
        }
        return res;
    }

}

性能

2785.将字符串中的元音字母排序

目标

给你一个下标从 0 开始的字符串 s ,将 s 中的元素重新 排列 得到新的字符串 t ,它满足:

  • 所有辅音字母都在原来的位置上。更正式的,如果满足 0 <= i < s.length 的下标 i 处的 s[i] 是个辅音字母,那么 t[i] = s[i] 。
  • 元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的,对于满足 0 <= i < j < s.length 的下标 i 和 j ,如果 s[i] 和 s[j] 都是元音字母,那么 t[i] 的 ASCII 值不能大于 t[j] 的 ASCII 值。

请你返回结果字母串。

元音字母为 'a' ,'e' ,'i' ,'o' 和 'u' ,它们可能是小写字母也可能是大写字母,辅音字母是除了这 5 个字母以外的所有字母。

示例 1:

输入:s = "lEetcOde"
输出:"lEOtcede"
解释:'E' ,'O' 和 'e' 是 s 中的元音字母,'l' ,'t' ,'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序,辅音字母留在原地。

示例 2:

输入:s = "lYmpH"
输出:"lYmpH"
解释:s 中没有元音字母(s 中都为辅音字母),所以我们返回 "lYmpH" 。

说明:

  • 1 <= s.length <= 10^5
  • s 只包含英语字母表中的 大写 和 小写 字母。

思路

有一个只包含英文字母的字符串,将其中的元音字母的位置按照 ASCII 码大小排序。

判断元音字母可以使用哈希表或者位运算。收集元音字母可以使用优先队列或者 StringBuilder 转成 charArray 之后再排序。

代码


/**
 * @date 2025-09-11 9:26
 */
public class SortVowels2785 {

    public static boolean[] isVowel = new boolean[26];

    static {
        isVowel[0] = true;
        isVowel['e' - 'a'] = true;
        isVowel['i' - 'a'] = true;
        isVowel['o' - 'a'] = true;
        isVowel['u' - 'a'] = true;
    }

    public String sortVowels(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (isVowel[Character.toLowerCase(c) - 'a']) {
                sb.append(c);
            }
        }
        char[] vowels = sb.toString().toCharArray();
        Arrays.sort(vowels);
        int j = 0;
        for (int i = 0; i < chars.length; i++) {
            if (isVowel[Character.toLowerCase(chars[i]) - 'a']) {
                chars[i] = vowels[j++];
            }
        }
        return new String(chars);
    }

}

性能

3403.从盒子中找出字典序最大的字符串I

目标

给你一个字符串 word 和一个整数 numFriends。

Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合,在每一回合中:

  • word 被分割成 numFriends 个 非空 字符串,且该分割方式与之前的任意回合所采用的都 不完全相同 。
  • 所有分割出的字符串都会被放入一个盒子中。

在所有回合结束后,找出盒子中 字典序最大的 字符串。

示例 1:

输入: word = "dbca", numFriends = 2
输出: "dbc"
解释: 
所有可能的分割方式为:
"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。

示例 2:

输入: word = "gggg", numFriends = 4
输出: "g"
解释: 
唯一可能的分割方式为:"g", "g", "g", 和 "g"。

提示:

  • 1 <= word.length <= 5 * 10^3
  • word 仅由小写英文字母组成。
  • 1 <= numFriends <= word.length

思路

word 划分为 numFriends 个非空子串,求字典序最大的子串。

找字典序最大的首字母,如果存在多个需要比较后面字符的字典序,还要保证能够划分成非空子串。

先找到字符串中字典序最大的字符集合作为起点,将其后面的字符放入优先队列 [char, index],根据字符从大到小排序,取队首连续相同的字符,将其后一个字符放到下一轮处理。

也可以不用手动逐个比较字符,枚举字典序最大的字符作为左端点,然后尽可能地扩展字符串长度 n - numFriends + 1,将结果收集后排序即可。

代码


/**
 * @date 2025-06-04 9:19
 */
public class AnswerString3403 {

    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        int n = word.length();
        List<Integer>[] chars = new ArrayList[26];
        Arrays.setAll(chars, x -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            chars[c - 'a'].add(i);
        }
        int l = n - numFriends + 1;
        String[] strs = null;
        for (int i = 25; i >= 0; i--) {
            if (chars[i].size() > 0) {
                strs = new String[chars[i].size()];
                for (int j = 0; j < chars[i].size(); j++) {
                    int index = chars[i].get(j);
                    strs[j] = word.substring(index, Math.min(index + l, n));
                }
                break;
            }
        }
        Arrays.sort(strs);
        return strs[strs.length - 1];
    }

}

性能