高效求解排序拼接子串指定索引字符问题（三种场景）

给定字符串 s 和整数 i，需生成 s 的所有连续子串，将这些子串排序后拼接为新字符串，要求高效查找新字符串中索引 i 处的字符。具体分为三种场景：

• 输入字符均唯一；
• 输入字符不唯一，但以位置作为排序破局规则（如acab中第一个a的排序优先级高于第二个a）；
• 输入字符不唯一且无排序破局规则（相同字符视为等价）。

示例 #

以字符串dbac为例，所有连续子串为：d、db、dba、dbac、b、ba、bac、a、ac、c。将这些子串排序后拼接得到新字符串：aacbbabaccddbdbadbac，当i=2时，返回字符c。

低效实现（O(n³)时间复杂度） #

以下是引发该问题的Java实现代码，其时间复杂度为O(n³)：

public char solve(String s, int m) {
    int n = s.length();
    List<String> list = new ArrayList<>();
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<=n; j++) {
            list.add(s.substring(i,j));
        }
    }
    Collections.sort(list);
    for(String s1 : list) {
        int q = s1.length();
        if(m >= q) m -= q;
        else {
            return s1.charAt(m);
        }
    }
    return ' ';
}

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