Given a string s, find the length of the longest substring with all distinct characters.
Examples:
Input: s = "geeksforgeeks" Output: 7 Explanation: "eksforg" is the longest substring with all distinct characters.
Input: s = "aaa" Output: 1 Explanation: "a" is the longest substring with all distinct characters.
Input: s = "abcdefabcbb" Output: 6 Explanation: The longest substring with all distinct characters is "abcdef", which has a length of 6.
Constraints:
1<= s.size()<=3*104
All the characters are in lowercase.
Approach 01:
-
C++
-
Python
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int longestUniqueSubstr(string &inputString) {
int windowStart = 0, windowEnd = 0; // Pointers for the sliding window
unordered_set<char> seenCharacters; // Set to store unique characters in the current window
int maxLength = 0; // Tracks the length of the longest substring without repeating characters
while (windowEnd < inputString.size()) {
if (seenCharacters.find(inputString[windowEnd]) != seenCharacters.end()) {
// If the current character is already in the set, shrink the window from the start
while (inputString[windowStart] != inputString[windowEnd]) {
seenCharacters.erase(inputString[windowStart]);
windowStart++;
}
windowStart++; // Move past the repeated character
} else {
// Add the character to the set if it's not already present
seenCharacters.insert(inputString[windowEnd]);
}
// Move the window end and update the maximum length
windowEnd++;
maxLength = max(maxLength, windowEnd - windowStart);
}
return maxLength; // Return the length of the longest unique substring
}
};
class Solution:
def longestUniqueSubstr(self, inputString: str) -> int:
windowStart = 0 # Pointer for the start of the sliding window
windowEnd = 0 # Pointer for the end of the sliding window
seenCharacters = set() # Set to store unique characters in the current window
maxLength = 0 # Tracks the length of the longest substring without repeating characters
while windowEnd < len(inputString):
if inputString[windowEnd] in seenCharacters:
# If the current character is already in the set, shrink the window from the start
while inputString[windowStart] != inputString[windowEnd]:
seenCharacters.remove(inputString[windowStart])
windowStart += 1
windowStart += 1 # Move past the repeated character
else:
# Add the character to the set if it's not already present
seenCharacters.add(inputString[windowEnd])
# Move the window end and update the maximum length
windowEnd += 1
maxLength = max(maxLength, windowEnd - windowStart)
return maxLength # Return the length of the longest unique substring
Time Complexity:
- Sliding Window Iteration:
The window expands and contracts, with each character being processed at most twice (once when added and once when removed). This results in \( O(n) \), where \( n \) is the length of the input string.
- Set Operations:
Inserting and erasing characters from the unordered set takes \( O(1) \) on average for each operation.
- Overall Time Complexity:
\( O(n) \).
Space Complexity:
- Unordered Set:
The unordered set stores characters from the input string. In the worst case, the set can hold all distinct characters, resulting in \( O(k) \), where \( k \) is the size of the character set (e.g., 26 for lowercase English letters).
- Input String:
The input string does not require additional space as it is read-only.
- Overall Space Complexity:
\( O(k) \).