This content originally appeared on DEV Community and was authored by Ashwat RK
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
This content originally appeared on DEV Community and was authored by Ashwat RK