Leetcode 3: Longest Substring Without Repeating Characters
grid47 Exploring patterns and algorithms
Nov 6, 2024
5 min read
Solution to LeetCode 3: Longest Substring Without Repeating Characters Problem
Given a string, determine the length of the longest substring that contains no repeating characters. The substring must consist of consecutive characters, and its length is to be returned as the output.
Problem
Approach
Steps
Complexity
Input: The input is a single string 's'.
Example: s = "abcdeabc"
Constraints:
• 0 <= s.length <= 50,000
• s consists of English letters, digits, symbols, and spaces.
Output: The output is an integer representing the length of the longest substring without repeating characters.
Example: 5
Constraints:
• The output must be a non-negative integer.
• If the string is empty, return 0.
Goal: To find the maximum length of a substring with unique characters from the given string.
Steps:
• Use a sliding window approach with two pointers to track the current substring.
• Maintain a hash map to store the most recent index of each character.
• Move the right pointer to include new characters and adjust the left pointer to avoid duplicates.
• Keep track of the maximum length of the substring during the process.
• Return the maximum length found.
Goal: The input string can contain a mix of characters, and the function should handle varying lengths efficiently.
Steps:
• The string can include any printable characters.
• The function should handle strings with up to 50,000 characters.
Assumptions:
• The input is a valid string.
• Special characters, digits, and spaces are treated the same as letters.
• Input: s = "abcdefabc"
• Explanation: The longest substring without repeating characters is "abcdef" with a length of 6.
• Input: s = "aaaaaa"
• Explanation: The longest substring without repeating characters is "a" with a length of 1.
• Input: s = "dvdf"
• Explanation: The longest substring without repeating characters is "vdf" with a length of 3.
Approach: A sliding window technique with a hash map to efficiently find the longest substring without repeating characters.
Observations:
• Using a brute force approach would result in a quadratic time complexity, which is not efficient for large strings.
• A sliding window with a hash map can efficiently track the unique characters in the current substring.
• Track the current substring using two pointers and maintain the last seen index of each character to avoid revisiting characters.
Steps:
• Initialize two pointers: `left` and `right`, both starting at 0.
• Use a hash map to store the last index of each character.
• Iterate through the string with the `right` pointer:
• If the current character is already in the hash map, update `left` to the maximum of its current value or the next index after the last occurrence of the character.
• Update the hash map with the current character's index.
• Calculate the length of the current substring and update the maximum length if necessary.
• Return the maximum length after the iteration is complete.
Empty Inputs:
• If the string is empty, the output should be 0.
Large Inputs:
• The function should handle strings with the maximum length efficiently.
Special Values:
• Strings with all unique characters should return the length of the string.
• Strings with all identical characters should return 1.
Constraints:
• Handles a mix of letters, digits, symbols, and spaces.
intlengthOfLongestSubstring(string s) {
int prv =-1, len =0;
map<char, int> mp;
for(int i =0; i < s.size(); i++) {
if(mp.count(s[i]))
prv = max(prv, mp[s[i]]);
mp[s[i]] = i;
len = max(len, i - prv);
}
return len;
}
1 : Function Declaration
intlengthOfLongestSubstring(string s) {
Declares a function `lengthOfLongestSubstring` that takes a string `s` as input and returns the length of the longest substring without repeating characters.
2 : Variable Initialization
int prv =-1, len =0;
Initializes two integer variables: `prv` to track the index of the last occurrence of a character, and `len` to store the length of the current longest substring.
3 : Map Initialization
map<char, int> mp;
Initializes an empty hash map `mp` to store characters as keys and their corresponding indices as values.
4 : Loop Initialization and Condition
for(int i =0; i < s.size(); i++) {
Starts a loop to iterate through each character in the string `s`.
5 : Character Check
if(mp.count(s[i]))
Checks if the current character `s[i]` is already present in the hash map.
6 : Update Previous Index
prv = max(prv, mp[s[i]]);
If the character is found, updates `prv` to the maximum of its current value and the previous index of the character.
7 : Update Character Index
mp[s[i]] = i;
Updates the index of the current character in the hash map.
8 : Update Longest Substring Length
len = max(len, i - prv);
Updates the `len` variable to the maximum of its current value and the length of the current substring, which is calculated as `i - prv`.
9 : Return Result
return len;
Returns the length of the longest substring without repeating characters.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each character is processed at most twice: once when moving the right pointer and once when adjusting the left pointer.
Best Case: O(m)
Worst Case: O(m)
Description: The space complexity depends on the size of the character set used in the string, where m is the maximum number of unique characters.
