CTCI

April 2021

1.2: Given two strings, write a method to decide if one is a permutation of the other.

• Check details: case sensitive, whitespace significant?

• Insight: strings of different lengths cannot be permutations

• Solution 1: sort the strings

• Solution 2: check if the strings have identical character counts

  • Use a 128 int array that functions like a hashmap for freq

    • Assuming ASCII character set

      • I always seem to assume that a string problem deals only with letters...

  • Then loop through the second string and, using the same array, decrement the freqs

    • If the two strings are equal, the array will be all 0 at the end

    • If at any point there is a negative freq, then we can immediately terminate

1.3: Write a method to replace all spaces in a string with '%20'. Perform this operation in place.

• Common approach in string manipulation problems is to edit the string starting from the end and working backward

• Implement using character arrays since Java strings are immutable

• Create a helper method to count the number of occurrences of a character within a start/end index of a char array

  • Use this to count number of spaces from 0 to the "true length" of the string that is given

  • Our final index of the final string will be trueLength - 1 + (numberOfSpaces *2)

    • We need to multiply by 2 because each space will require 2 extra characters