Problem
Given a string s, find the length of the longest substring without repeating characters.
Input
String s consisting of English letters, digits, symbols and spaces.
Output
Length of the longest substring without repeating characters of string s
Constraints
- 0 <= Length of s ≤ 5 * 104
Sample Input
s = "pwwkew"
Sample Output
3 The answer is "wke", with the length of 3.
Solution
Approach: Sliding Window Technique and Hashing
Code Implementation
class Solution {
public:
int lengthOfLongestSubstring (string s) {
int *charMap = new int[300]();
int n = s.size();
int maxSoFar = 0;
int maxSol = 0;
int prev = 0;
if (s.size() <= 1) {
return s.size();
}
for (int i=0; i<300; i++) {
charMap[i] = -1;
}
for (int i=0; i<n; i++) {
if (charMap[s[i]] == -1) {
maxSoFar++;
charMap[s[i]] = i;
} else {
prev = max(prev, charMap[s[i]]);
maxSoFar = i-prev;
charMap[s[i]] = i;
}
maxSol = max(maxSol, maxSoFar);
}
return maxSol;
}
};
Time complexity: O(n), where n is the length of string s