String¶
Table of Contents¶
- 125. Valid Palindrome (Easy)
- 242. Valid Anagram (Easy)
- 409. Longest Palindrome (Easy)
- 3. Longest Substring Without Repeating Characters (Medium)
- 8. String to Integer (atoi) (Medium)
- 5. Longest Palindromic Substring (Medium)
- 438. Find All Anagrams in a String (Medium)
- 76. Minimum Window Substring (Hard)
125. Valid Palindrome¶
# List Comprehension
def isPalindrome(s: str) -> bool:
s = [char.lower() for char in s if char.isalnum()]
return s == s[::-1]
# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
s = "A man, a plan, a canal: Panama"
print(isPalindrome(s)) # True
print(isPalindromeLR(s)) # True
242. Valid Anagram¶
"""
- Return true if an input string is an anagram of another string.
- An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once, e.g., `listen` is an anagram of `silent`.
"""
from collections import Counter
# Hashmap
def isAnagramHash(s: str, t: str) -> bool:
"""Return True if t is an anagram of s, False otherwise."""
if len(s) != len(t):
return False
count = dict()
for i in s:
if i in count:
count[i] += 1
else:
count[i] = 1
for j in t:
if j in count:
count[j] -= 1
else:
return False
for count in count.values():
if count != 0:
return False
return True
# Array
def isAnagramArray(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0 for _ in range(26)]
for i in s:
count[ord(i) - ord("a")] += 1
for j in t:
count[ord(j) - ord("a")] -= 1
for i in count:
if i != 0:
return False
return True
# Counter
def isAnagramCounter(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
# |-------------|-----------------|--------------|
# | Approach | Time | Space |
# |-------------|-----------------|--------------|
# | Hashmap | O(n) | O(1) |
# | Array | O(n) | O(1) |
# | Counter | O(n) | O(1) |
# |-------------|-----------------|--------------|
s = "anagram"
t = "nagaram"
print(isAnagramHash(s, t)) # True
print(isAnagramArray(s, t)) # True
print(isAnagramCounter(s, t)) # True
#include <cassert>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
vector<int> count(26, 0);
for (char ch : s) count[ch - 'a']++;
for (char ch : t) count[ch - 'a']--;
for (int c : count) {
if (c != 0) return false;
}
return true;
}
};
int main() {
Solution solution;
assert(solution.isAnagram("anagram", "nagaram") == true);
assert(solution.isAnagram("rat", "car") == false);
assert(solution.isAnagram("a", "ab") == false);
assert(solution.isAnagram("a", "a") == true);
return 0;
}
409. Longest Palindrome¶
"""
- Return the length of the longest palindrome that can be built with the characters in the string.
"""
def longestPalindrome(s: str) -> int:
hashmap = dict()
result = 0
for char in s:
if char not in hashmap or hashmap[char] == 0:
hashmap[char] = 1
else:
result += 2
hashmap[char] = 0
if any(hashmap.values()):
result += 1
return result
print(longestPalindrome("abccccdd")) # 7
3. Longest Substring Without Repeating Characters¶
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""Sliding Window: O(n) time, O(min(n, charset)) space.
Jump the left edge past each repeated character's previous index.
"""
left = 0
res = 0
seen = {}
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
res = max(res, right - left + 1)
return res
def lengthOfLongestSubstringSet(self, s: str) -> int:
"""Sliding Window Set: O(n) time, O(min(n, charset)) space.
Shrink until the current character is unique in the window.
"""
left = 0
res = 0
window = set()
for right, ch in enumerate(s):
while ch in window:
window.remove(s[left])
left += 1
window.add(ch)
res = max(res, right - left + 1)
return res
def test_length_of_longest_substring():
s = Solution()
cases = [
("abcabcbb", 3),
("bbbbb", 1),
("pwwkew", 3),
("", 0),
(" ", 1),
("abba", 2),
("dvdf", 3),
]
for text, expected in cases:
assert s.lengthOfLongestSubstring(text) == expected
assert s.lengthOfLongestSubstringSet(text) == expected
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
int n = s.length();
int res = 0;
int left = 0;
unordered_set<char> window;
for (int right = 0; right < n; right++) {
char ch = s[right];
while (window.find(ch) != window.end()) {
window.erase(s[left]);
left++;
}
window.insert(ch);
res = max(res, right - left + 1);
}
return (int)res;
}
int main() {
string s = "abcabcbb";
cout << lengthOfLongestSubstring(s) << endl; // 3
s = "bbbbb";
cout << lengthOfLongestSubstring(s) << endl; // 1
s = "pwwkew";
cout << lengthOfLongestSubstring(s) << endl; // 3
return 0;
}
8. String to Integer (atoi)¶
5. Longest Palindromic Substring¶
class longestPalindrome:
"""Return the longest palindromic substring in s."""
@staticmethod
def dp(s: str) -> str:
n = len(s)
if n <= 1:
return s
start, maxLen = 0, 1
# Init
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
# update
for j in range(1, n):
for i in range(j):
if s[i] == s[j]:
if j - i <= 2:
dp[i][j] = 1
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and j - i + 1 > maxLen:
maxLen = j - i + 1
start = i
return s[start : start + maxLen]
@staticmethod
def expand_around_center(s: str) -> str:
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
if len(s) <= 1:
return s
start, end = 0, 0
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
maxLen = max(odd, even)
if maxLen > end - start:
start = i - (maxLen - 1) // 2
end = i + maxLen // 2
return s[start : end + 1]
if __name__ == "__main__":
s = "babad"
assert longestPalindrome.dp(s) in ["bab", "aba"]
assert longestPalindrome.expand_around_center(s) in ["bab", "aba"]
438. Find All Anagrams in a String¶
from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
"""Fixed Sliding Window: O(n + m) time, O(1) space.
Track 26 lowercase counts for the current window of length len(p).
"""
if len(p) > len(s):
return []
target = [0] * 26
window = [0] * 26
for i, ch in enumerate(p):
target[ord(ch) - ord("a")] += 1
window[ord(s[i]) - ord("a")] += 1
res = []
if window == target:
res.append(0)
left = 0
for right in range(len(p), len(s)):
window[ord(s[right]) - ord("a")] += 1
window[ord(s[left]) - ord("a")] -= 1
left += 1
if window == target:
res.append(left)
return res
def test_find_anagrams():
s = Solution()
assert s.findAnagrams("cbaebabacd", "abc") == [0, 6]
assert s.findAnagrams("abab", "ab") == [0, 1, 2]
assert s.findAnagrams("af", "be") == []
assert s.findAnagrams("baa", "aa") == [1]
assert s.findAnagrams("", "a") == []
76. Minimum Window Substring¶
from collections import Counter
def minWindow(s: str, t: str) -> str:
if not t or not s:
return ""
counts = Counter(t)
required = len(counts)
left, right = 0, 0
formed = 0
window_counts = dict()
result = float("inf"), None, None
while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in counts and window_counts[char] == counts[char]:
formed += 1
while left <= right and formed == required:
char = s[left]
if right - left + 1 < result[0]:
result = (right - left + 1, left, right)
window_counts[char] -= 1
if char in counts and window_counts[char] < counts[char]:
formed -= 1
left += 1
right += 1
return "" if result[0] == float("inf") else s[result[1] : result[2] + 1]
s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t)) # BANC