LeetCode ๐๏ธ/String
LeetCode ๐๏ธ/String
647. Palindromic Substrings
Description: Solution: In for loop, we have two parts: odd number length & even number length. In odd number case, we expand our l & r pointers to both sides, and get the number of palindromic. In even number case, we do same thing, but l & r pointer starts with different location. (i, i+1)
LeetCode ๐๏ธ/String
5. Longest Palindromic Substring
Description: Solution: Brute Force --> time complexity will be O(n^3). However, it takes a lot of time. Instead of Brute Force, we are gonna set left & right pointer for the string. In the for loop, we are gonna check if the string is odd number length or not. We keep update the resLen, and make sure it should be bigger than previous resLen. In odd number case, l & r starts from s[0]. We keep mo..
LeetCode ๐๏ธ/String
125. Valid Palindrome
Description: Solution: Let's make left pointer & right pointer. isalnum() makes sure the char is whether char or not. If one of those is not char, then we move the pointer. Space Complexity: O(1)
LeetCode ๐๏ธ/String
20. Valid Parentheses
Description: Solution: In pariHash, we set close parentheses as a key, and open parentheses as a value. If the c is open parentheses, we append on stack. If the c is closing parentheses, we search the last value of stack "stack[-1]" and compare it with its key. We can pop the stack. If the stack is empty at the end of the solution, we can return True. Time Complexity: O(n) Space Complexity: O(n)
LeetCode ๐๏ธ/String
49. Group Anagrams
Description: Solution: We use hashtable for this problem. In hashtable, the key is the sorted value(ex. aet, ant, abt in example 1) if keyString is not the key in table, we make the new list for it. Then, we append s to the appropriate key. Time Complexity: O(m*nlogn) Space Complexity: O(n)
LeetCode ๐๏ธ/String
242. Valid Anagram
Description: Solution: We use soft() to rearrange the character. See "s == t".
LeetCode ๐๏ธ/String
76. Minimum Window Substring
Description: Solution: countT, window will be what we "have" & what we "need" We update our window[c]. Does window[c] satisfiy 'window[c] == countT'? Time Complexity: O(n)
LeetCode ๐๏ธ/String
424. Longest Repeating Character Replacement
Description: Solution: count will store the number of letters of each chracters. res is the longest length of substring we can have. There will be two pointers: r, l Moving r pointer, we count the character. If the length(substring) - (count of bigger character) is bigger than k, we should move l pointer. Then, update the max res. Time Complexity: O(n)
LeetCode ๐๏ธ/String
3. Longest Substring Without Repeating Characters
Description: Solution: We use set() for substring. (Sliding Window) In example 1, the string is abcabcbb. We are gonna store substring until meet duplicated character. abc -> now we meet "a" Remove the first "a", now new substring is bca. The length of substring should be r - l + 1. Time Complexity: O(n) Space Complexity: O(n)
