java - 具有原始字符串的所有不同字符的最小长度子字符串的滑动窗口解决方案

Question

谁能告诉我哪里出错了。下面是我的代码。这里我使用滑动窗口解决方案，左和右作为指向字符串的指针。“dist_count”包含字符串中唯一字符的计数。

public class Solution {
    public String findSubstring(String s) {
        if (s == null || s.length() == 0)
            return "";
        int dist_count = 0;
        int[] hash = new int[256]; // character hash
        boolean[] visited = new boolean[256];
        // record each character in s to hash
        for (char c : s.toCharArray()) {
            hash[c]++;
        }
        for (char c : s.toCharArray()) {
            if (visited[c] == false) {
                dist_count++;
                visited[c] = true;
            }
        }
        System.out.println(dist_count);
        int left = 0, right = 0, count = 0;
        int min_window = Integer.MAX_VALUE;
        int startIndex = -1;
        while (right < s.length()) {
            if (hash[s.charAt(right)] >= 1) {
                count++;
            }
            hash[s.charAt(right)]--;
            right++;

            if (count == dist_count) {
                while (hash[s.charAt(left)] > 1) {
                    if (hash[s.charAt(left)] > 1)
                        hash[s.charAt(left)]--;
                    left++;
                }
                int window = right - left + 1;
                if (min_window > window) {
                    min_window = window;
                    startIndex = left;
                }
            }
        }
        return s.substring(startIndex, startIndex + min_window);
    }

    public static void main(String args[]) {
        Solution ob = new Solution();
        String str = ob.findSubstring("abdacbfcabegbdfcadcefa");
        System.out.println(str);
    }
}

Answer 1

您的算法是正确的，但在实现过程中存在一些问题。您不应该使用原始字符串中剩余的散列。看下面的代码:

for(int i = 0; i < 256; ++i) hash[i] = 0;  // Before entering while reset hash
                                           // counters for sliding window
while (right < s.length()) {
    if (hash[s.charAt(right)] == 0) {  // Use hash here for counting frequency
        count++;
}
hash[s.charAt(right)]--;  // Consistently increment for right and decrement for left

Working code有上述变化