-
-
Save parcar/f9385e26de7b308e4480c2b3b9945bdd to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution(object): | |
| def lengthOfLongestSubstring(self, s): | |
| """ | |
| :type s: str | |
| :rtype: int | |
| """ | |
| ''' | |
| Intuition: | |
| Iterate through each letter in the string, and evaluate it as a starting position for the longest substring | |
| For each letter, iterate starting at that letter until reaching a repeat or the end of substring | |
| ''' | |
| cmax = 0 | |
| for idx, letter in enumerate(s): | |
| #Reset set and count variables | |
| cset = set() | |
| count = 0 | |
| for ss in s[idx:]: | |
| #print(locals()) | |
| #Early termination condition | |
| if (len(s[idx:]) < cmax): | |
| return cmax | |
| elif (ss in cset): | |
| #End current substring | |
| break | |
| else: | |
| count += 1 | |
| cmax = count if count > cmax else cmax | |
| cset.add(ss) | |
| return cmax |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment