Problem:
Given a string s, find the length of the longest substring without repeating characters.
Example:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Solution:
#include <iostream>
#include <unordered_map>
#include <algorithm>
int lengthOfLongestSubstring(std::string s)
{
std::unordered_map<char, int> charIndexMap;
int maxLength = 0;
int start = 0;
for (int end = 0; end < s.length(); ++end)
{
if (charIndexMap.find(s[end]) != charIndexMap.end())
{
// If the character is already in the substring, update the starting index.
start = std::max(charIndexMap[s[end]] + 1, start);
}
// Update the index of the current character.
charIndexMap[s[end]] = end;
// Update the maximum length if needed.
maxLength = std::max(maxLength, end - start + 1);
}
return maxLength;
}
int main()
{
std::string s = "abcabcbb";
int result = lengthOfLongestSubstring(s);
std::cout << "Output: " << result << std::endl;
return 0;
}
Complexity:
Time complexity: O(n)
Space complexity: O(min(m, n)), where n is the length of the string and m is the size of the character set (number of distinct characters)
Explanation:
The solution uses a sliding window approach with two pointers, start and end, to traverse the string. The charIndexMap is used to keep track of the last index at which each character appeared. If a repeating character is found, the start pointer is updated to the next index after the last occurrence of the repeating character.