java在不重复字符的情况下查找最长子字符串的长度

Question

所以我要解决的问题是，给定一个字符串，求出最长子字符串的长度，而不需要重复字符。我知道基于HashMap的解决方案，但在子字符串重叠的情况下，它会失败。这是我的密码

public static int lengthOfLongestSubstring(String s) {

        Deque<Character> primary = new ArrayDeque<>();
        Deque<Character> secondary = new ArrayDeque<>();

        for (int i = 0; i < s.length() ; i++) {
            char c = s.charAt(i);
            if(primary.contains(c)){
                while(primary.peek() != c){
                    secondary.offerLast(primary.poll());
                }
                secondary.offerFirst(c);
                primary = secondary;
                secondary.clear();
            }else{
                primary.offerFirst(c);
            }
        }
        return primary.size();

    }

这在我做primary = secondary的地方失败了，否则我认为我在逻辑上做得对。 为了测试正确性，我使用了字符串dvdf 有人能帮我理解为什么这不起作用吗

Answer 1

可能不是你想要的确切答案。尽量避免在多线程环境中使用ArrayDeque，因为它不是线程安全的

通过以下链接：

Find longest substring without repeating characters

这将返回一个字符串。你可以用。方法，并根据需要查找长度

希望能有帮助

Answer 2

/*C++ program to print the largest substring in a string without repetation of character.
eg. given string :- abcabbabcd
largest substring possible without repetition of character is abcd.*/

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str,str1;
    int max =0;
    string finalstr;
    vector<string> str2;
    cin>>str;
    int len = str.length();
    for(int i=0;i<len;i++)
    {
        if(str1.find(str[i]) != std::string::npos)
        {
            str2.push_back(str1);
            char p = str[i];
            str1 = "";
            i--;
            while(p!=str[i])
                i--;
        }
        else
            str1.append(str,i,1);
    }
    str2.push_back(str1);

    for(int i=0;i<str2.size();i++)
    {
        if(max<str2[i].length()){
            max = str2[i].length();
            finalstr  = str2[i];
        }
    }
    cout<<finalstr<<endl;
    cout<<finalstr.length()<<endl;
}

Answer 3

我想知道：

primary = secondary;
secondary.clear();

这是参考作业。您可以将primary和secondary设置为指向相同的数据并将其清除。这是你的意图吗

那么这个呢：

public static int lengthOfLongestSubstring(String s) {

    Deque<Character> primary = new ArrayDeque<>();
    Deque<Character> secondary = new ArrayDeque<>();
    Deque<Character> longest = new ArrayDeque<>();

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (primary.contains(c)) {
            // Store longest
            if (primary.size() > longest.size()) {
                longest = new ArrayDeque<>(primary);
            }

            while (primary.peek() != c) {
                secondary.offerLast(primary.poll());
            }
            secondary.offerFirst(c);
            primary = secondary;
            secondary = new ArrayDeque<>();  // Altered
        } else {
            primary.offerFirst(c);
        }
    }

    // Also check at end of line.
    if (primary.size() > longest.size()) {
        longest = primary;
    }

    return longest.size();
}

输出

• dvdf=>；三,
• dvdfvadv=>；四,

编辑

你的逻辑是正确的。我刚改了一行

编辑

记录最长的时间

Answer 4

您可以尝试以下方法：

public class LongestSubstring {
    public static void main(String [] args){
        System.out.println(longestSub("abcdefgghij"));
//prints 7 abcdefg g is repeated character
    }
    public static int longestSub(String s) {
        if(s==null)
            return 0;
        boolean[] flag = new boolean[256];

        int result = 0;
        int start = 0;
        char[] arr = s.toCharArray();

        for (int i = 0; i < arr.length; i++) {
            char current = arr[i];
            if (flag[current]) {
                result = Math.max(result, i - start);
                // the loop update the new start point and reset flag array

                for (int k = start; k < i; k++) {
                    if (arr[k] == current) {
                        start = k + 1;
                        break;
                    }
                    flag[arr[k]] = false;
                }
            } else {
                flag[current] = true;
            }
        }

        result = Math.max(arr.length - start, result);

        return result;
    }
}