Longest Substring Without Repeating Characters

Problem Statement

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

---

Approach

To solve this problem, we can use the sliding window technique along with a dictionary to keep track of the most recent index of each character.

---

Steps

1. Initialize Variables

• last_position (dictionary): Stores the last seen index of each character.
• max_length (integer): Tracks the length of the longest substring without repeating characters. Initialize it to 0.
• prev (integer): Marks the starting index of the current substring window. Initialize it to 0.

---

2. Iterate Through the String

Use a for loop to iterate over the string with an index i and the current character s[i].

1. Check for Repeating Characters:

   • If s[i] is found in last_position and last_position[s[i]] >= prev:
     • Update prev to last_position[s[i]] + 1 to move the starting index of the window after the last occurrence of the character.

2. Update the Window and Variables:

   • Update last_position[s[i]] to the current index i.
   • Calculate the current substring length: i - prev + 1.
   • Update max_length if the current substring length is greater.

---

3. Return the Result

After the loop, max_length contains the length of the longest substring without repeating characters.

---

Example Input and Output

Example 1

Input:
s = "abcabcbb"

Output:
3

Explanation:
The longest substring without repeating characters is "abc", with a length of 3.

---

Example 2

Input:
s = "bbbbb"

Output:
1

Explanation:
The longest substring without repeating characters is "b", with a length of 1.

---

Example 3

Input:
s = "pwwkew"

Output:
3

Explanation:
The longest substring without repeating characters is "wke", with a length of 3.

---

Test Cases

Test Case 1

Input:
s = "abcde"

Output:
5

Explanation:
All characters are unique, so the longest substring is the entire string.

Test Case 2

Input:
s = ""

Output:
0

Explanation:
The string is empty, so the longest substring length is 0.

Test Case 3

Input:
s = "abba"

Output:
2

Explanation:
The longest substrings without repeating characters are "ab" or "ba", both with a length of 2.

---

Constraints

1. 0 <= s.length <= 10^5
2. s consists of English letters, digits, symbols, and spaces.

— Written by Saurabh Patil • B.Tech CSE • Software Developer