Search for a command to run...
An example of using a sliding window approach and an unordered map to track character positions
Hi! My name is Nhut Nguyen. I am a software engineer and a writer in Copenhagen, Denmark.
Learn more about me at nhutnguyen.com
A simple example of using C++ switch
Two dynamic programming techniques to solve Leetcode 120. Triangle. One has space complexity O(n^2). The other is O(n).
A simple C++ solution to Leetcode 1695. Maximum Erasure Value using a sliding window approach and prefix sums.
Strategies to avoid them will help you excel in your following technical interview
Given a string s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with a length of 3.
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with a length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
0 <= s.length <= 5 * 10^4.
s consists of English letters, digits, symbols and spaces.
One way of checking the repetition of the characters is by using a map to store their indices. For example:
last_visit[s[i]] = i
You might want to find every substring of nonrepeating characters in the string s, then identify the longest one among them.
The character you are checking its repetition and computing the length should be done within its substring;
The map should always update the latest visited index of a character; and
The starting index of a substring is also updated when repetition happens.
For the string s = "abcabcbb":
When you visit the second letter 'a', the first substring is formed "abc", the next substring starts from the second letter 'a': start = 3 , last_visit['a'] is updated to be 3.
When you visit the second letter 'b', its last_visit['b'] is updated to be 4.
Repetition is found when you visit the third letter 'b', the second substring "abc" is formed. The next start = 6; last_visit['b'] = 6.
The fourth letter 'b' causes a repetition and forms a one-letter substring "b".
The string s ends and form another one-letter substring "b".
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> last_visit;
int maxLen = 0;
int start = -1;
for (int i = 0; i < s.length(); i++) {
auto it = last_visit.find(s.at(i));
if (it != last_visit.end()) {
start = max(start, it->second);
it->second = i;
} else {
last_visit.insert({s.at(i), i});
}
maxLen = max(maxLen, i - start);
}
return maxLen;
}
int main() {
cout << lengthOfLongestSubstring("abcabcbb") << endl;
cout << lengthOfLongestSubstring("bbbbb") << endl;
cout << lengthOfLongestSubstring("pwwkew") << endl;
}
Output:
3
1
3
Runtime: O(N), where N = s.length.
Extra space: O(N).
You can initialize the start index of the substrings with -1 to deal with the boundary cases.
As a best practice, when you check if a map contains a key and retrieve its value, use an iterator and find() like the above solution. DO NOT implement as follow
if (last_visit.find(s.at(i)) != last_visit.end()) {
start = max(start, last_visit[s.at(i)]);
}
Because the operator [] might perform an additional find().
Thanks for reading. Feel free to share your thought about my content and check out my book10 Classic Coding Challenges for FREE: