代码来查找最长的唯一K字符子字符串,不适用于所有输入 [英] code to find longest substring with unique K characters not working for all inputs
问题描述
给出一个字符串 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
这篇关于代码来查找最长的唯一K字符子字符串,不适用于所有输入的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!