String

1. In-place Manipulation (similar to in-place manipulation for array)

   1. usually use two pointer: a slow pointer and a fast pointer

   2. If the output has smaller size than the input, loop forward.

   3. If the output has larger size than the input, assign the full size first and then loop backward.

   4. If the output may have smaller or larger size, assign a new array may be easier than in-place manipulation.

   5. Example questions:

      1. 833_Find And Replace in String

2. Two pointer

   1. One slow, one fast

   2. One loop forward, one loop backward (usually used when we need to check symmetric properties)

   3. Example questions:

      1. 125_Valid Palindrome

      2. 680_Valid Palindrome II

3. Multiple passes

   1. In some questions, using one pass is hard to complete everything. In this case, we can try two passes or more.

   2. Example questions:

      1. 151_Reverse Words in a String

4. Use hash table/dictionary

   1. If when loop over each element in the string, we need to do a second loop over (at least part of) the string such that these two loops together meets the condition, we can only do one loop and use hash table / set to store the corresponding information.

   2. Example questions:

      1. 387_First Unique Character in a String

Note:

1. String is immutable. They don't support element assignment. It's wrong to write x = "abc" x[1] = "e"

2. When handling string problems, since string is immutable, the common practice is to convert string to array first, then deal with the array. To return a string output, we can further joint the array output into a string.