CODEWITHSUNDEEP
javastring
Zeus
Zeus

Reputation: 2253

Find the length of the longest substring without repeating characters

So the problem I'm trying to solve this problem given a string, find the length of the longest substring without repeating characters. I'm aware of the HashMap based solution, but that fails in case of overlapping substrings.Here's my code.

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();

    }

This fails at the line where I do primary = secondary otherwise I think I'm doing it right logically. To test the correctness I'm using the string dvdf Can someone help me understand why this is not working.

Upvotes: 2

Views: 1288

Answers (4)

Vivek Mutha
Vivek Mutha

Reputation: 29

/*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;
}

Upvotes: 0

totoro
totoro

Reputation: 2456

I am wondering this:

primary = secondary;
secondary.clear();

It's assignment by reference. You set primary and secondary to point to the same data and clear it. Is that your intention?

What about this:

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();
}

OUTPUT

  • dvdf => 3
  • dvdfvadv => 4

EDIT

Your logic is right. I just altered one line.

EDIT

Keep track of the longest.

Upvotes: 1

Fikru Mengesha
Fikru Mengesha

Reputation: 1

You can try this:

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;
    }
}

Upvotes: 0

Abhishek
Abhishek

Reputation: 2525

May not be exact answer you were looking. Try to avoid using ArrayDeque in a multi threaded env as it is not thread safe.

Go through this link::

Find longest substring without repeating characters

this returns a string. you can use .length() method and find the length as you require.

Hope it helps.

Upvotes: 1

Related Questions