[Medium] Given a string s, find the length of the longest substring without repeating characters.
s = "abcabcbb" => 3. The longest substring is "abc" or "bca"... , which both have the length of 3.
s = "bbbbbb" => 1
s = "pwwkew" => 3 ("wke")
Use i and j to indicate the start and end index of the substring(sliding window strategy). The target is to make sure the substring s[i, j] doesn't have repeating characters. Move j forward by 1 and check if the next character exists in the substring. Every time index is moved, work out the current longest length of the substring.
For example: "abcba"
-
"[a]bcba" Check if next character 'b' is in substring 'a' - No.(length = 1)
-
"[ab]cba" Check if next character 'c' is in substring 'ab' - No.(length = 2)
-
"[abc]ba" Check if next character 'b' is in substring 'abc' - Yes.(length = 3) 3.1 Move the start index forward. "a[bc]ba" Check if the next character 'b' is in substring 'bc' - Yes.(length = 2) 3.2 Move(again) the start index forward. "ab[c]ba" Check if the next character 'b' is in substring 'c' - No.(length = 1)
-
"ab[cb]a" Check if the next character 'a' is in substring 'cb' - No.(length = 2)
-
"ab[cba]" The end of string (length = 3)
So the returned value is 3.
[Medium] Given a string s, return the longest palindromic substring.
s = "babad" => "aba" or "bab"
s = "abcde" => "a" One single letter itself is also a palindrome. Of course, other letters in this string is also the answer.
Iterate through the string. For a particular character, look at its left and right characters to check if they are equal. If they are equal, continue looking at their left/right characters(spreading) until hits the unequal characters.
Be careful that the middle character(s) can be one or two.
Be careful of the edge case when the given string is a single character string.
[Easy] A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
s = "A man, a plan, a canal: Panama" => true. "amanaplanacanalpanama" is a palindrome.
s = "race a car" => false. "raceacar" is not a palindrome.
s = " " => true. After removing non-alphanumeric characters, s becomes an empty string, which reads the same forward and backward.
Use two pointers, left and right, starting from the beginning and end of the string. Skip over any non-alphanumeric characters by moving the pointers inward. Compare the lowercased characters at left and right — if they differ, the string is not a palindrome. Otherwise, keep moving both pointers toward the middle until they meet.
[Medium] The string s is written in a zigzag pattern on a given number of rows like this (you may want to display this pattern in a fixed font for better legibility):
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR".
Write the function that will take a string and make this conversion given a number of rows: convert(s, numRows).
s = "PAYPALISHIRING", numRows = 3 => "PAHNAPLSIIGYIR"
s = "PAYPALISHIRING", numRows = 4 => "PINALSIGYAHRPI"
P I N
A L S I G
Y A H R
P I
s = "A", numRows = 1 => "A"
Simulate the zigzag by writing characters into numRows row buffers while bouncing a cursor between the top and bottom row. Start at row 0 moving downward. For each character, append it to the current row's buffer, then, if the cursor is at the top row (0) or the bottom row (numRows - 1), reverse direction. Move the cursor one row in the current direction and repeat. Once every character has been placed, concatenate the row buffers in order to get the result. When numRows is 1, no zigzag occurs, so the original string is returned unchanged.