Sliding Window is one of the most important interview techniques. Whenever a problem asks for the longest, shortest, or continuous subarray/substring, think about Sliding Window first. Using a HashMap allows us to jump directly to the previous occurrence of a character instead of checking every substring. This reduces the complexity from O(n²) to O(n).
Problem stats
Before
Generate every possible substring.
For each substring:
1. Check whether all characters are unique.
2. If unique, update the maximum length.
3. Continue checking all possible substrings.
This approach is simple but inefficient because it repeatedly checks duplicate characters.
After
Use the Sliding Window technique with a HashMap.
Maintain two pointers:
- left
- right
Move the right pointer one character at a time.
If a character already exists inside the current window,
move the left pointer just after its previous occurrence.
Update the maximum window size during each iteration.
This guarantees every character is processed only once.
The optimized implementation, ready for interview preparation and quick revision.
Solution.java
1import java.util.HashMap;2import java.util.Map;3 4public class Solution {5 6 public int lengthOfLongestSubstring(String s) {7 8 Map<Character, Integer> map = new HashMap<>();9 10 int left = 0;11 int maxLength = 0;12 13 for (int right = 0; right < s.length(); right++) {14 15 char current = s.charAt(right);16 17 if (map.containsKey(current) && map.get(current) >= left) {18 left = map.get(current) + 1;19 }20 21 map.put(current, right);22 23 maxLength = Math.max(maxLength, right - left + 1);24 }25 26 return maxLength;27 }28 29 public static void main(String[] args) {30 31 Solution solution = new Solution();32 33 System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));34 System.out.println(solution.lengthOfLongestSubstring("bbbbb"));35 System.out.println(solution.lengthOfLongestSubstring("pwwkew"));36 }37}Analyze the efficiency of the algorithm by understanding its time and space complexity across different execution scenarios.
Time complexity
Space complexity
By execution case
Best case
O(n)
Average case
O(n)
Worst case
O(n)
This solution achieves a O(n) time complexity while using O(min(n, m)) extra memory. It is considered the optimal approach for this problem and is suitable for coding interviews as well as competitive programming.
Every coding problem teaches a pattern. Focus on the concepts, avoid common mistakes, and remember the interview-worthy takeaways instead of memorizing code.
The biggest takeaway from this problem.
Sliding Window is one of the most important interview techniques. Whenever a problem asks for the longest, shortest, or continuous subarray/substring, think about Sliding Window first. Using a HashMap allows us to jump directly to the previous occurrence of a character instead of checking every substring. This reduces the complexity from O(n²) to O(n).
Explain why the optimized solution works before writing the final code. Interviewers care about your thinking process as much as your implementation.
Avoid jumping directly to coding. Always analyze edge cases, constraints, and the optimal approach before implementation.
Focus on understanding the algorithm's pattern instead of memorizing the code. Once the logic becomes clear, implementing the solution in any programming language becomes much easier.
Every DSA problem introduces a reusable pattern. Instead of remembering the exact solution, remember the thought process that led to it. Over time, these patterns will help you solve new problems much faster and perform better in coding interviews.
Practice consistently and move through the roadmap one problem at a time.
Next
Climbing Stairs
Practice similar problems to strengthen your understanding of the underlying algorithm and improve pattern recognition.