Longest substring with distinct characters

JavaView on GFG

Time: O(n)

Space: O(min(n,26))

Intuition

Sliding window with at most k distinct characters (or all distinct). HashSet tracks current window characters.

Algorithm

1Window [l,r] with set of characters.
2Expand r. If duplicate: shrink l until unique.
3Track max window size.

Common Pitfalls

•Set vs frequency map: set suffices if all distinct; map needed for generic k distinct.

Longest substring with distinct characters.java

Java

// Approach: Sliding window with a Set or char-to-index map. Shrink window on duplicate character.
// Time: O(n) Space: O(min(n,26))
class Solution {
    public int longestUniqueSubstr(String s) {
        boolean c[] = new boolean[26];
        int l = 0;
        int r = 0;
        int len = Integer.MIN_VALUE;
        int n = s.length();
        while (r < n) {
            if (c[s.charAt(r) - 'a']) {
                while (s.charAt(l) != s.charAt(r)) {
                    c[s.charAt(l) - 'a'] = false;
                    l++;
                }
                c[s.charAt(l) - 'a'] = false;
                l++;
            }
            c[s.charAt(r) - 'a'] = true;
            len = Math.max(len, r - l + 1);
            r++;
        }
        return len;
    }
}

Was this solution helpful?