java - 包含所有字母的不同字符的最短子字符串的长度

Question

给定一个由 ascii[az] 范围内的小写字母组成的字符串，其中每个字母代表一种硬币类型，确定包含每种类型硬币中至少一种的最短子字符串的整数长度，其中硬币保证至少包含一套完整的。
我的代码针对以下输入运行:
导入 java.util.*;

public class Program1 {

    public static void main(String args[]) {
        String str = "asdfkjeghfalawefhaef";
        System.out.println(shortestSubstring(str));
    }

    public static int shortestSubstring(String str) {
        List<Integer> list = new ArrayList<>();
        char[] c = str.toCharArray();
        int length = getDistinctLenght(str);
        for (int j = 0; j <= c.length - length; j++) {
            for (int i = 0; i < c.length; i++) {
                if (j + i + length <= c.length) {
                    String temp = str.substring(j, j + i + length);
                    if (getDistinctLenght(temp) == length) {
                        list.add(temp.length());
                    }
                }
            }
        }
        return Collections.min(list);
    }

    private static int getDistinctLenght(String str) {
        char[] c = str.toCharArray();
        Set<Character> set = new HashSet<>();
        for (Character a : c) {
            set.add(a);
        }
        return set.size();
    }

}

但它无法为大量输入运行: rfkqyuqfjkxyqvnrtysfrzrmzlygfveulqfpdbhlqdqrrcrwdnxeuoqqeklaitgdphcspijthbsfyfvladzpbfudkklrwqaozmixrpifeffeclhbvfukbyeqfqojwtwosileeztxwjlkngbqqmbxqcqptkhhqrqdwfcayssyoqcjomwufbdfxudzhiftakczvhsybloetswcrfhpxprbsshsjxdfilebxwbctoayaxzfbjbkrxirimqpzwmshlpjhtazhbuxhwadlptoyeziwkmgsovqzgdixrpdd什么可能是错的？

Answer 1

这是一个有趣的小问题。我没有分析你的程序，而是自己写的。它在 O(n) 中运行，其中 n 是字符串的长度。我希望你发现它仍然有用。
该程序的工作原理如下:在 for 循环中，它确定包含迄今为止看到的所有不同字符的最短子字符串，该子字符串恰好在索引 end 处结束。 .它通过跟踪 charCount 来做到这一点。每个字符在来自 start 的子字符串中出现的频率至 end .最多有 26 个不同的字符，因此该数组为每个字符提供了一个计数器。如果 start 处的字符在子串中出现不止一次，我们可以增加start (即省略第一个字符)而不会丢失任何内容，因为它必须至少再次出现在子字符串中。
运行时间显然是 O(n)，因为 end和 start do 只在算法过程中增加并且在 0 和 n 之间。

public class Main {

    public static void main(String[] args) {
        findSmallest("asdfkjeghfalawefhaef");
        findSmallest("rfkqyuqfjkxyqvnrtysfrzrmzlygfveulqfpdbhlqdqrrcrwdnxeuoqqeklaitgdphcspijthbs" +
                "fyfvladzpbfudkklrwqaozmixrpifeffeclhbvfukbyeqfqojwtwosileeztxwjlkngbqqmbxqcq" +
                "ptkhhqrqdwfcayssyoqcjomwufbdfxudzhiftakczvhsybloetswcrfhpxprbsshsjxdfilebxwb" +
                "ctoayaxzfbjbkrxirimqpzwmshlpjhtazhbuxhwadlptoyeziwkmgsovqzgdixrpdd");
    }

    private static void findSmallest(String in) {
        int start = 0;
        int[] charCount = new int[26];
        int differentChars = 0;
        int shortestLength = 0;
        for (int end = 0; end < in.length(); end++) {
            final int idx = in.charAt(end) - 'a';
            if (charCount[idx] == 0) {
                // we found a brand new character, previous minimum is invalid
                differentChars++;
                shortestLength = end - start + 1;
            }
            charCount[idx]++;
            // shorten the substring if possible
            while (charCount[in.charAt(start) - 'a'] > 1) {
                charCount[in.charAt(start) - 'a']--;
                start++;
                shortestLength = Math.min(shortestLength, end - start + 1);
            }
        }
        System.out.printf("there is a substring of length %d containing all %d different characters%n",
                shortestLength, differentChars);
    }
}

这是我为短输入和长输入示例得到的结果。

there is a substring of length 13 containing all 11 different characters
there is a substring of length 48 containing all 26 different characters

我也尝试了你的程序，它为这两个测试用例提供了相同的输出。