What is the time complexity of Longest Substring Without Repeating Characters?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Longest Substring Without Repeating Characters?

This problem uses Hash Table, String, Sliding Window. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Longest Substring Without Repeating Characters?

Insight 1: The problem can be solved efficiently using a sliding window approach. Insight 2: A hash table (or character array in the C version) can be used to keep track of the characters within the current window and their last seen positions.

Which companies ask LeetCode 3. Longest Substring Without Repeating Characters in interviews?

This problem is frequently asked at AMD, Accenture, Accolite, Adobe, Agoda and 87 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Substring Without Repeating Characters - LeetCode 3 Solution

Longest Substring Without Repeating Characters - Complete Solution Guide

Longest Substring Without Repeating Characters is LeetCode problem 3, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a string s , find the length of the longest substring without duplicate characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence

Detailed Explanation

The problem asks us to find the length of the longest substring within a given string that contains no repeating characters. A substring is a contiguous sequence of characters within a string. For example, in the string "abcabcbb", "abc" is a substring of length 3 without repeating characters, while "pwke" is a subsequence (not contiguous) of the string "pwwkew", and we're looking for substrings. The input is a string `s`, and the output is an integer representing the length of the longest substring without repeating characters. The string `s` can contain English letters, digits, symbols, and spaces, and its length can be between 0 and 5 * 10^4.

Solution Approach

The solution uses a sliding window technique along with a hash table (or array) to keep track of the last seen index of each character. The window expands to the right, and the hash table is updated with the character's index. If a repeating character is encountered within the current window, the left boundary of the window is moved to the right of the previous occurrence of that character. The maximum length of the substring without repeating characters is updated at each step.

Step-by-Step Algorithm

Step 1: Initialize a hash table (or array) `char_map` to store the last seen index of each character. Initialize the left pointer `left` to 0 and the maximum length `max_length` to 0.
Step 2: Iterate through the string `s` from left to right using the right pointer `right`.
Step 3: For each character `char` at index `right`, check if it exists in `char_map` and if its last seen index is within the current window (i.e., `char_map[char] >= left`).
Step 4: If the character is a duplicate within the current window, update the left pointer `left` to `char_map[char] + 1` to exclude the previous occurrence of the character from the current window.
Step 5: Update `char_map[char]` with the current index `right`.
Step 6: Update `max_length` with the maximum of the current `max_length` and the current window length (`right - left + 1`).
Step 7: After iterating through the entire string, return `max_length`.

Key Insights

Insight 1: The problem can be solved efficiently using a sliding window approach.
Insight 2: A hash table (or character array in the C version) can be used to keep track of the characters within the current window and their last seen positions.
Insight 3: When a repeating character is encountered, the left boundary of the window should be moved to the right of the previous occurrence of that character.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, String, Sliding Window.

Companies

Asked at: AMD, Accenture, Accolite, Adobe, Agoda, Airtel, Alibaba, Amazon, American Express, Apple, Atlassian, BNY Mellon, Bloomberg, ByteDance, Capgemini, Cisco, Cognizant, Comcast, Coupang, Dell, Deloitte, Docusign, EPAM Systems, Epic Systems, Expedia, Flipkart, Freecharge, FreshWorks, Goldman Sachs, Google, Grab, HCL, HPE, IBM, Infosys, Intel, Intuit, J.P. Morgan, Juspay, LinkedIn, Lucid, Lyft, MAQ Software, MakeMyTrip, Meta, Microsoft, Morgan Stanley, NCR, Nagarro, Netflix, Nike, Nvidia, Optum, Oracle, Ozon, Palo Alto Networks, PayPal, Paytm, PornHub, Publicis Sapient, Qualcomm, Roblox, SOTI, Salesforce, ServiceNow, Snowflake, Softwire, Spotify, Tesla, ThoughtWorks, TikTok, Tinkoff, Turing, Uber, Veeva Systems, Virtusa, Visa, Walmart Labs, Wipro, Yahoo, Yandex, Yelp, ZScaler, Zeta, Zoho, Zynga, athenahealth, eBay, josh technology, opentext, persistent systems, tcs.

Longest Substring Without Repeating Characters | LeetCode 3

Medium

Hash Table String Sliding Window

Time: O(n)Space: O(1)

Solution Code

Available in:

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charMap = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            if (charMap.containsKey(currentChar) && charMap.get(currentChar) >= left) {
                left = charMap.get(currentChar) + 1;
            }

            charMap.put(currentChar, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3: Longest Substring Without Repeating Characters - Detailed explanation and solution approaches.

Topics

Hash Table String Sliding Window

Companies

AMDAccentureAccoliteAdobeAgodaAirtelAlibabaAmazon

Stats

Difficulty:Medium

Languages:4

Companies:92

Problem #:3

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize a hash table (or array) `char_map` to store the last seen index of each character. Initialize the left pointer `left` to 0 and the maximum length `max_length` to 0.
2
Step 2: Iterate through the string `s` from left to right using the right pointer `right`.
3
Step 3: For each character `char` at index `right`, check if it exists in `char_map` and if its last seen index is within the current window (i.e., `char_map[char] >= left`).
4
Step 4: If the character is a duplicate within the current window, update the left pointer `left` to `char_map[char] + 1` to exclude the previous occurrence of the character from the current window.
5
Step 5: Update `char_map[char]` with the current index `right`.
6
Step 6: Update `max_length` with the maximum of the current `max_length` and the current window length (`right - left + 1`).
7
Step 7: After iterating through the entire string, return `max_length`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because each character in the input string is visited at most twice (once by the right pointer and at most once by the left pointer). The space complexity is O(1) because the size of the hash table is limited by the character set (ASCII or Unicode), which is independent of the input string length.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible substrings and check if each substring has repeating characters. Keep track of the longest substring without repeating characters.

Time: O(n^3), where n is the length of the string.Space: O(n), where n is the length of the string, to store the substrings.

Trade-offs: This approach is simple to understand but inefficient for larger strings due to its high time complexity. It should be avoided for practical use.

Sliding Window with Set

Similar to the main solution, but using a set to track characters in the current window. When a repeating character is found, remove characters from the left of the window until the repeating character is removed.

Time: O(n), where n is the length of the string.Space: O(n), in worst case all characters in string s are unique and stored in Set.

Trade-offs: Space complexity of this approach can be higher when string contains unique characters. However, readability can be easier than the main solution.

✨

Key Insights

1Insight 1: The problem can be solved efficiently using a sliding window approach.
2Insight 2: A hash table (or character array in the C version) can be used to keep track of the characters within the current window and their last seen positions.
3Insight 3: When a repeating character is encountered, the left boundary of the window should be moved to the right of the previous occurrence of that character.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string. The solution correctly handles the empty string case because the loop won't execute, and the initial value of `max_length` (0) will be returned.
Edge case 2: String with all repeating characters (e.g., "bbbbb"). The solution correctly identifies the longest substring as a single character, returning 1.
Edge case 3: String with only unique characters (e.g., "abcdefg"). The solution correctly identifies the entire string as the longest substring, returning the length of the string.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly updating the left pointer when a repeating character is encountered. The left pointer must be moved to the right of the previous occurrence of the repeating character, not just to the next index.

✗Common mistake 2: Failing to handle the case where the repeating character is outside the current window (i.e., `char_map[char] < left`). In this case, the left pointer should not be moved.

✗Common mistake 3: Not understanding the difference between a substring (contiguous sequence) and a subsequence (not necessarily contiguous).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression algorithms. Finding patterns and repeating sequences helps in efficient data compression.

🏦Real-world scenario 2: Bioinformatics. Identifying unique sequences of DNA or RNA is essential in analyzing genetic information.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 4, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Longest Substring Without Repeating Characters"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?