Longest Substring Without Repeating Characters

Created on: Jan 16, 2025

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

import java.util.*;

public class Solution {
    public static String longestUniqueSubstring(String s) {
       return null;
    }

    public static void main(String[] args) {

        boolean test = true;

        test = test && longestUniqueSubstring("aaabcbdeaf").equals("cbdeaf");

        // Basic cases
        test = test && longestUniqueSubstring("aaabcbdeaf").equals("cbdeaf");
        test = test && longestUniqueSubstring("abcabcbb").equals("abc");
        test = test && longestUniqueSubstring("bbbbb").equals("b");

        // Empty string
        test = test && longestUniqueSubstring("").equals("");

        // All unique characters
        test = test && longestUniqueSubstring("abcdef").equals("abcdef");

        // No repeated characters
        test = test && longestUniqueSubstring("pqrstuv").equals("pqrstuv");

        // Repeated patterns
        test = test && longestUniqueSubstring("abababab").equals("ab");

        // Longest unique substring at the end
        test = test && longestUniqueSubstring("aabcde").equals("abcde");

        // Single character string
        test = test && longestUniqueSubstring("a").equals("a");

        // String with non-alphabetic characters
        test = test && longestUniqueSubstring("a1b2c3d4!").equals("a1b2c3d4!");

        // String with mixed characters
        test = test && longestUniqueSubstring("aabc1234xyz123").equals("abc1234xyz");

        // String with special characters
        test = test && longestUniqueSubstring("a!@#$%^&*()b").equals("a!@#$%^&*()b");

        if (test) {
            System.out.println("pass");
        } else {
            System.out.println("Fail");
        }
    }
}

Solution

public static String longestUniqueSubstring(String s) {
    int n = s.length();
    int left = 0, right, start = 0;
    int maxLen = 0;

    Set<Character> set = new HashSet<>();

    for (right = 0; right < n; right++) {
        char c = s.charAt(right);
        if (set.contains(c)) {
            left++;
        }
        set.add(c);
        if ((right - left + 1) > maxLen) {
            maxLen = right - left + 1;
            start = left;
        }
    }
    return s.substring(start, start + maxLen);
}

Reference

leetcode