Today, I decided to challenge myself with LeetCode Problem 3: Longest Substring Without Repeating Characters. As someone who enjoys solving algorithmic problems, I thought this would be a walk in the park—a cup of coffee while coding, so to speak.
Well… I was in for a little surprise.
After writing my initial solution, I ran it against the LeetCode test cases. Out of 988 cases, 987 passed. But one stubborn test case failed. I realized it was probably a load test meant to check how efficient my solution really was. Even though it didn’t fully pass, this exercise taught me a lot about handling substrings, avoiding repeated characters, and thinking about efficiency.
Let me walk you through my journey.
Understanding the Problem
The problem sounds simple at first:
Given a string, find the length of the longest substring without repeating characters.
For example:
• "abcabcbb" → Longest substring: "abc" → length = 3
• "bbbbb" → Longest substring: "b" → length = 1
• "pwwkew" → Longest substring: "wke" → length = 3
Sounds easy, right? But implementing it efficiently is a bit tricky.
My First Attempt
Here’s the first function I wrote:
var lengthOfLongestSubstring = function (str) {
let arr = str.split('');
let mainLeft = 0;
let subLeft = 0;
let right = subLeft + 1;
let subStrArr = [];
let subStr = 0;
subStrArr.push(arr[subLeft]);
while (mainLeft < arr.length) {
if (right < arr.length) {
if ((!(arr[subLeft] === arr[right])) & !subStrArr.includes(arr[right])) {
subStrArr.push(arr[right]);
right++;
} else {
if (subStrArr.length > subStr) subStr = subStrArr.length;
subStrArr = [];
subLeft = right;
subStrArr.push(arr[subLeft]);
right++;
}
} else {
if (subStrArr.length > subStr) subStr = subStrArr.length;
mainLeft++;
subStrArr = [];
subLeft = mainLeft;
subStrArr.push(arr[subLeft]);
right = subLeft + 1;
}
}
return subStr;
};
At first glance, it’s messy—but each part has a purpose. Here’s the breakdown:
Step 1: Preparing the String
let arr = str.split('')
I converted the string into an array of characters to make it easier to access individual elements. For example, "abc" becomes ['a', 'b', 'c'].
Step 2: Defining Pointers
let mainLeft = 0;
let subLeft = 0;
let right = subLeft + 1;
• mainLeft: Keeps track of where to start exploring new substrings.
• subLeft: Marks the start of the current substring without repeats.
• right: Moves forward to expand the substring until a repeat is found.
Step 3: Tracking Substrings
let subStrArr = [];
let subStr = 0;
subStrArr.push(arr[subLeft]);
• subStrArr keeps the current substring we are building.
• subStr stores the length of the longest substring found so far.
Step 4: Iterating Through the String
I used a while loop to explore all possible substrings starting from mainLeft. Inside, I either expand the substring or reset it when a repeated character shows up.
Step 5: Expanding and Resetting
When the current character isn’t in subStrArr, I add it and move right forward. If it’s a repeat, I check if the current substring is the longest, reset, and start from the next position.
Reflection
The solution worked for most cases, but it failed on the load test. Why?
• Using an array and includes check is O(n) for each character.
• Nested iterations make the worst-case O(n²).
For large strings, this approach becomes inefficient.
The Efficient Solution: Sliding Window
Here’s the optimized solution I found on the LeetCode discussion:
var lengthOfLongestSubstring = function (s) {
let set = new Set();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
How It Works
- Sliding Window:
o We keep a “window” [left, right] of non-repeating characters.
o left moves forward if a duplicate is found. - Using a Set:
o set.has() and set.delete() are O(1), so we avoid scanning the substring repeatedly. - Expanding and Contracting:
o Move right forward to include new characters.
o If a repeat is found, remove characters from left until it’s gone. - Updating Maximum Length:
- maxLen = Math.max(maxLen, right - left + 1);
o This calculates the current substring length and updates the maximum.
________________________________________
Complexity
• Time Complexity: O(n) → each character is processed at most twice.
• Space Complexity: O(min(n, m)) → m is the character set size (e.g., 128 for ASCII).
Conclusion
Solving this problem was an eye-opener. My first solution worked but wasn’t efficient. The sliding window approach not only passes all test cases but also handles large strings efficiently.
This exercise reinforced the importance of:
• Using appropriate data structures
• Thinking about time complexity
• Sliding window technique for substring problems