如何生成字典序大于给定输入字符串的目标字符串

核心实现逻辑 #

我们可以生成所有满足A < B的字符串中长度最短、字典序最小的结果，从根源避免资源浪费，具体步骤如下：

• 空字符串处理：直接返回包含单个最小字符（可根据你使用的字符集调整，默认取字符类型的最小值）的字符串，因为空串字典序小于所有非空串
• 非空字符串从后向前遍历，查找第一个值小于字符集最大值的字符：
  • 找到后将该字符值+1，删除该位置之后的所有字符，即可得到目标B
  • 如果所有字符都等于字符集最大值，则在字符串末尾追加1个最小字符即可

示例（假设字符集为小写字母a-z，最小值a，最大值z）：
输入为"abc"：从后找到第一个非最大值的字符c，加1得到d，输出"abd"
输入为"abz"：末尾z是最大值，向前找到b，加1得到c，删除后续的z，输出"ac"
输入为"zzz"：所有字符都是最大值，末尾加a，输出"zzza"

方案优势 #

完全解决你提到的三个问题：

• 空输入有单独处理逻辑
• 只有确认字符未达取值上限时才会执行+1操作，不会出现溢出导致B < A的问题
• 仅当原字符串所有字符都是最大值时才会增加长度，不会出现快速生成超长字符串的问题

标准库说明 #

目前没有跨语言的通用标准库函数实现该需求，因为逻辑本身非常简单，且依赖你使用的字符集取值范围，自行实现的成本极低。

参考实现（C++） #

#include <string>
#include <limits>

std::string next_lex_string(const std::string& A) {
    using CharT = unsigned char;
    constexpr CharT min_c = std::numeric_limits<CharT>::min();
    constexpr CharT max_c = std::numeric_limits<CharT>::max();

    if (A.empty()) {
        return std::string(1, static_cast<char>(min_c));
    }

    std::string B = A;
    for (int i = B.size() - 1; i >= 0; --i) {
        auto c = static_cast<CharT>(B[i]);
        if (c < max_c) {
            B[i] = static_cast<char>(c + 1);
            B.resize(i + 1);
            return B;
        }
    }

    // 所有字符都是最大值，追加最小字符
    B += static_cast<char>(min_c);
    return B;
}

内容的提问来源于stack exchange，提问作者Lorah Attkins