Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Longest substring without repeating characters challenge

Sharing is caring!

Problem statement
Given a string, find the length of the longest substring without repeating characters.

Examples

Example 1
Given abcabcbb, the answer is abc, which the length is 3.

Example 2
Given bbbbb, the answer is b, with the length of 1.

Example 3
Given pwwkew, the answer is wke, with the length of 3. Note that the answer must be a substring, pwke is a subsequence and not a substring.

Solution

public class LongestSubstringWithoutRepeatingChar {
    static public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set set = new HashSet();
        int ans = 0;

        int start = 0;
        for (int i = 0; i < n; i++) {
            if (!set.contains(s.charAt(i))) {
                set.add(s.charAt(i));
            } else {
                // We have already added the character to our substring

                ans = Math.max(ans, i - start);

                boolean found = false;
                do {
                    found = s.charAt(start) == s.charAt(i);
                    set.remove(s.charAt(start));
                    start++;
                } while (!found);

                set.add(s.charAt(i));
            }
        }


        return Math.max(ans, n - start);
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("c"));
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        System.out.println(lengthOfLongestSubstring("au"));
    }
}