Topic 02 of 15
String
Letters on a bead necklace.
A string is a row of letters, like beads on a necklace. Everything that works on arrays works here, plus a few new tricks: counting letters in a notebook, sliding a window over the necklace, and matching a small word inside a big one.
What you will be able to do
Character countsSliding windowPalindromesPattern matching (KMP, Rabin Karp)DP on two strings
0/43
Meet the string
01 / 05
The word level is five beads: l, e, v, e, l.
- checking
- done
- answer
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Reverse a StringTurn a word around so the last letter comes first, by swapping letters from both ends toward the middle.Two pointers
- 02Check whether a String is Palindrome or notCheck if a word reads the same from the front and from the back, by walking in from both ends at once.Two pointers
- 03Find Duplicate characters in a stringFind every letter that shows up more than once in a string, and how many times, by keeping a tally sheet as you read.Hash map counting
- 04Why strings are immutable in JavaA Java String is like a word carved in stone: nobody can change it, so everyone can safely share it, and a change always makes a new stone.Immutable objects
- 05Write a Code to check whether one string is a rotation of anotherCheck if one word is another word that was turned like a necklace, by writing the first word twice and looking for the second inside it.String doubling
- 06Write a Program to check whether a string is a valid shuffle of two strings or notCheck if a string was made by shuffling two strings together like two decks of cards, where each deck keeps its own order.2D dynamic programming
- 07Count and Say problemBuild each new number by reading the last one out loud in groups, like three ones, two twos, one one, and writing down what you hear.Run length counting
- 08Write a program to find the longest Palindrome in a string - Longest palindromic SubstringFind the longest stretch of a word that reads the same forwards and backwards, by growing outwards from every possible middle.Expand around center
- 09Find Longest Recurring Subsequence in StringFind the longest word you can spell twice inside one string, picking letters in order, where the two spellings never use the same spot.2D dynamic programming
- 10Print all Subsequences of a stringList every way to keep some letters of a word and drop the rest, without changing their order.Backtracking
- 11Print all the permutations of the given stringList every order the letters of a word can stand in, by choosing who goes first, then who goes second, and so on.Backtracking
- 12Split the Binary string into two substring with equal 0s and 1sCut a row of 0s and 1s into as many pieces as you can, so that every piece has as many 0s as 1s.Running balance
- 13Word Wrap ProblemBreak a list of words into lines of a fixed width so the empty space at the line ends is as even as possible, where big gaps cost a lot more than small ones.1D dynamic programmingMust do
- 14EDIT DistanceFind the fewest single letter changes (add one, remove one, or swap one) that turn one word into another, using a chart of smaller answers.2D dynamic programmingMust do
- 15Find next greater number with same set of digitsShuffle the digits of a number to make the very next bigger number, by finding the rightmost dip, swapping in a slightly bigger digit, and flipping the tail.Next permutationMust do
- 16Balanced Parenthesis problemCheck that every opening bracket gets closed by the right partner, in the right order, like doors you walk back out of.StackMust do
- 17Word break ProblemCheck if a long string with no spaces can be cut into pieces that are all real words from a word list.1D dynamic programmingMust do
- 18Rabin Karp AlgoFind a short word inside a long text by comparing quick number fingerprints first, and reading letters only when the fingerprints agree.Rolling hash
- 19KMP AlgoFind every place a short word appears inside a long text, without ever stepping back in the text, by remembering how the word repeats itself.Prefix function (KMP)
- 20Convert a Sentence into its equivalent mobile numeric keypad sequenceTurn a sentence into the button presses you would make on an old phone keypad, where pressing a key more times picks a later letter.Lookup table
- 21Minimum number of bracket reversals needed to make an expression balancedTurn the fewest curly brackets around so that every opening bracket gets its own closing partner.Stack matching
- 22Count All Palindromic Subsequence in a given StringCount every way to pick some letters, in order, that reads the same forwards and backwards, by building answers for short stretches first.2D dynamic programming
- 23Count of number of given string in 2D character arrayCount every way to spell a word on a letter grid by stepping between touching boxes, never using a box twice, and stepping back at dead ends.Backtracking
- 24Search a Word in a 2D Grid of charactersFind every box in a letter grid where a word starts, reading in a straight line in any of the eight directions, like a word search puzzle.Grid direction scan
- 25Boyer Moore Algorithm for Pattern SearchingSlide a little word along a long text to find every place it appears, checking from its last letter so a wrong letter lets you jump far ahead.Pattern matching with skips
- 26Converting Roman Numerals to DecimalTurn Roman letters like MCMXCIV into a normal number by adding each letter, except a small letter right before a bigger one, which is taken away.Look ahead by one
- 27Longest Common PrefixFind the longest start that every word in a list shares, by reading all the words together one letter at a time.Column by column scan
- 28Number of flips to make binary string alternateCount the fewest 0 and 1 flips that make a row of digits take turns, like 0101 or 1010.Compare with a target
- 29Find the first repeated word in stringRead a sentence word by word and report the first word you meet for a second time, using a bag of words you have already seen.Hash set lookup
- 30Minimum number of swaps for bracket balancingCount how many times neighbors must trade places so every closing bracket has an opening bracket before it.Greedy counting
- 31Find the longest common subsequence between two stringsFind the longest list of letters that both strings contain in the same order, skipping letters as needed, using a chart of smaller answers.2D dynamic programming
- 32Program to generate all possible valid IP addresses from given stringCut a string of digits into four numbers from 0 to 255, in every legal way, to make internet addresses.Backtracking
- 33Write a program to find the smallest window that contains all characters of string itselfFind the shortest stretch of a string that still contains every different letter the whole string has.Sliding window
- 34Rearrange characters in a string such that no two adjacent are sameShuffle the letters of a word so that no two neighbors are the same, by always using the letter with the most copies left.Greedy with a heap
- 35Minimum characters to be added at front to make string palindromeCount the fewest letters to stick on the front of a word so it reads the same forwards and backwards.Prefix function (KMP)
- 36Given a sequence of words, print all anagrams togetherPut words made of the same letters into the same group, by giving every word a label that its letter twins share.Hash map grouping
- 37Find the smallest window in a string containing all characters of another stringFind the shortest stretch of a long word that still holds every letter on your shopping list.Sliding window
- 38Recursively remove all adjacent duplicatesLetters that sit next to an identical twin pop like bubbles, the gap closes, and new twins that meet pop too, until no twins are left.Stack
- 39String matching where one string contains wildcard charactersCheck if a pattern with joker cards, where ? stands for any one letter and * for any run of letters, can cover a whole word exactly.2D dynamic programming
- 40Function to find Number of customers who could not get a computerRead a string of arrivals and goodbyes at a computer shop and count how many customers were sent away because every computer was busy.Hash map counting
- 41Transform One String to Another using Minimum Number of Given OperationTurn one word into another by picking up letters and putting them at the front, using as few moves as possible.Two pointers from the end
- 42Check if two given strings are isomorphic to each otherCheck if one word can turn into another by swapping each letter for a fixed partner letter, where no two letters share a partner.Two hash maps
- 43Recursively print all sentences that can be formed from list of word listsMake every sentence you can by picking one word from each list, in order, like choosing one item from each row of a menu.Backtracking