代码来查找最长的唯一K字符子字符串，不适用于所有输入

本文介绍了代码来查找最长的唯一K字符子字符串，不适用于所有输入的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个字符串 aabbcdeeeeggi并且k = 3，代码应找到最长的子字符串，最多包含k个唯一字符。对于上述输入，它应该是 deeeeggi。

Given a String, ""aabbcdeeeeggi" and k=3, the code should find longest substring with maximum of k unique characters. For the above input, it should be "deeeeggi".

这里是一个优雅的O（n） Python中的问题的解决方案。我正在Java中实现，但没有获得所有输入的期望输出。

Here is an elegant O(n) solution for the problem in Python. I am implementing in Java. but I am not getting the desired output for all the inputs.

public class SubStringWithKUniqueCharacters { public static void main(String[] args){ System.out.println(longestSubStringWithUniqueK("aabbcdeeeeggi", 3)); System.out.println(longestSubStringWithUniqueK("aabbcdeeeeggi", 2)); } public static String longestSubStringWithUniqueK(String input, int k){ int len = input.length(); Set<Character> unique = new HashSet<>(); int i = 0; int j = 0; int count = 0; int maxStartIndex = 0; int maxEndIndex = 0; int maxLen = 0; char[] inputArr = input.toCharArray(); while (i<len){ if (count==k && j -i > maxLen){ maxStartIndex = i; maxEndIndex = j; maxLen = maxEndIndex - maxStartIndex; } if (count<k && j<len){ if (unique.add(inputArr[j])){ count++; } j++; } else { if (unique.remove(inputArr[i])){ count--; } i++; } } return input.substring(maxStartIndex,maxEndIndex); } }

这是输出：

eeeeggi //correct output eeeggi //incorrect output

我无法捕获错误所在。任何帮助将非常感激。 谢谢

I am not able to capture where the bug is. Any help would be much appreciated. Thanks

推荐答案

您的实现无法按预期方式运行，原因是原始的python解决方案存在错误。我对您的代码做了一些修改。希望现在一切正常：

Your implementation does not work the way as expected, is because the original python solution has bug. I made some modifications to your code. Hope it's now all right:

public class SubStringWithKUniqueCharacters { public static void main(String[] args){ System.out.println(longestSubStringWithUniqueK("aabbcdeeeeggi", 3)); System.out.println(longestSubStringWithUniqueK("aabbcdeeeeggi", 2)); } public static String longestSubStringWithUniqueK(String input, int k){ int len = input.length(); Set<Character> unique = new HashSet<>(); int i = 0; int j = 0; int count = 0; int maxStartIndex = 0; int maxEndIndex = 0; int maxLen = 0; char[] inputArr = input.toCharArray(); while (i<len){ if (count==k && j -i > maxLen){ maxStartIndex = i; maxEndIndex = j; maxLen = maxEndIndex - maxStartIndex; } // 1. if we reach the end of the string, we're done. if (j + 1 > len){ break; } // 2. changed to count <= k here else if (count<= k && j<len){ if (unique.add(inputArr[j])){ count++; } j++; } else { if (unique.remove(inputArr[i])){ // 3. remove all consecutive chars of the same value char c = inputArr[i]; // save as temp char while (inputArr[i] == c) { i++; } count--; } } } return input.substring(maxStartIndex,maxEndIndex); } }

现在的输出为：

deeeegg eeeegg