Han Zhu's Study Notes

Given a string, find the length of the  longest substring  without repeating characters. Examples: Given  "abcabcbb" , the answer is  "abc" , which the length is 3. Given  "bbbbb" , the answer is  "b" , with the length of 1. Given  "pwwkew" , the answer is  "wke" , with the length of 3. Note that the answer must be a  substring ,  "pwke"  is a  subsequence  and not a substring. Thought process: Two pointers + sliding window: Pointer i points to the left end of current window. Pointer j points to the right end of current window. Use a hash set to keep track of the characters in current window. Iterate through the string using j. If s[j] is a repeating character, increment i and remove s[i] from set until no repeating character is there. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int lengthOfLongestSubstring ( String s ) { ...

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note: The input string length won't exceed 1000. Thought process: Dynamic programming. Use a matrix to check if s[i,j] is a palindrome. If so, add one to count. Sub-problem: check if a sub-string of s is a palindrome. Function:  If s[i] == s[j]: If j - i < 2 (one character or two characters), f[i][j] = true. Otherwise, f[i][j] = f[i + 1][j - 1]. Otherwise, f[i][j] = false. Initialization: none. Answer: f[0][n - 1] will sa...

Validate if a given string is numeric. Some examples: "0"  =>  true " 0.1 "  =>  true "abc"  =>  false "1 a"  =>  false "2e10"  =>  true Note:  It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. Thought process: There are several rules to enforce: There must be at least one number. e must come after some number and be followed by some number. Point cannot come after e. + and - can only appear in two positions: at the start of the string or right after e. There cannot be characters other than digits, e, point, + or -, or space. We can use several boolean flags to make these happen. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public boolean isNumber ( String s ) { s = s . trim (); boolea...

Given a string, we can "shift" each of its letter to its successive letter, for example:  "abc" -> "bcd" . We can keep "shifting" which forms the sequence: "abc" -> "bcd" -> ... -> "xyz" Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence. For example, given:  ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"] , A solution is: [ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ] Thought process: Hash table. If two strings belong to the same shifting sequence, the differences between any consecutive pair of their characters are the same. We can use those differences as encoding for the strings. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...

Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced. We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert dashes. Additionally, all the lower case letters in the string must be converted to upper case. So, you are given a non-empty string S, representing a license key to format, and an integer K. And you need to return the license key formatted according to the description above. Example 1: Input: S = "2-4A0r7-4k", K = 4 Output: "24A0-R74K" Explanation: The string S has been split into two part...

Given a string, find the length of the longest substring T that contains at most  k  distinct characters. For example, Given s =  “eceba”  and k = 2, T is "ece" which its length is 3. Thought process: Sliding window. Use a hash map of character => integer to keep track of the count of each character in the current window. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int lengthOfLongestSubstringKDistinct ( String s , int k ) { Map < Character , Integer > map = new HashMap <>(); int i = 0 ; int longest = 0 ; for ( int j = 0 ; j < s . length (); j ++) { int count = map . getOrDefault ( s . charAt ( j ), 0 ); map . put ( s . charAt ( j ), count + 1 ); if ( map . size () > k ) { while ( i < s . length () && ...

Suppose we abstract our file system by a string in the following manner: The string  "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"  represents: dir subdir1 subdir2 file.ext The directory  dir  contains an empty sub-directory  subdir1  and a sub-directory  subdir2  containing a file  file.ext . The string  "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"  represents: dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext The directory  dir  contains two sub-directories  subdir1  and  subdir2 .  subdir1  contains a file  file1.ext  and an empty second-level sub-directory  subsubdir1 .  subdir2  contains a second-level sub-directory  subsubdir2  containing a file  file2.ext . We are interested in finding the longest (number of characters) absolu...

Given a non-empty string  s , you may delete  at most  one character. Judge whether you can make it a palindrome. Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000. Thought process: Two pointers. One starts from the beginning and one from the end. Use a flag to check if a character has been deleted. If there's a character difference and no deletion has happened yet, set the flag to true and call recursively. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public boolean validPalindrome ( String s ) { return validPalindrome ( s , 0 , s . length () - 1 , false ); } private boolean validPalindrome ( String s , int left , int right , boolean deleted ) { whi...

Given two strings S and T, determine if they are both one edit distance apart. Thought process: Check if S and T are one insertion or replacement away. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public boolean isOneEditDistance ( String s , String t ) { if ( s . equals ( t )) { return false ; } return isOneInsert ( s , t ) || isOneReplace ( s , t ); } private boolean isOneInsert ( String s , String t ) { if ( Math . abs ( s . length () - t . length ()) != 1 ) { return false ; } boolean inserted = false ; int i = 0 ; int j = 0 ; while ( i < s . length () && j < t . length ()) { if ( s . charAt ( i ) != t . charAt ( j )) { ...