Longest Substring Without Repeating Characters

ghz 10months ago ⋅ 76 views

To find the length of the longest substring without repeating characters, you can use a sliding window approach. Here's a Java implementation:

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeatingCharacters {

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(start, map.get(c) + 1); // Move start pointer to the right of the previous occurrence of c
            }
            map.put(c, end); // Update the latest position of character c
            maxLength = Math.max(maxLength, end - start + 1); // Update the maximum length
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Length of the longest substring without repeating characters: " + lengthOfLongestSubstring(s)); // Output: 3
    }
}

In this implementation:

  • We use a sliding window approach with two pointers start and end.
  • The start pointer marks the start of the current substring without repeating characters.
  • The end pointer moves through the string to explore substrings.
  • We maintain a HashMap to store the latest position of each character in the string.
  • If we encounter a character that is already in the HashMap, we update the start pointer to the right of the previous occurrence of that character.
  • We update the maximum length of the substring (maxLength) as we traverse through the string.
  • Finally, we return the maxLength, which represents the length of the longest substring without repeating characters.
  • We test the implementation with an example string and print the length of the longest substring without repeating characters.
#algorithm