**Problems**:

| No.   | Problem                                                      | Difficulty | Date                       | Time Spent | Key   Point                                                  | Diffcult Point                                 | Similar Problem                                              | Note                                                         |
| ----- | ------------------------------------------------------------ | ---------- | -------------------------- | ---------- | ------------------------------------------------------------ | ---------------------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 0006  | [ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion/) | Medium     | 2020-11-9<br />2020-12-18  |            |                                                              | How to convert the original String to ZigZag ? | Vertical Word ?                                              | Refer to solution(12-18)                                     |
| 0008  | [String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/) | Medium     | 2020-11-10<br />2020-12-21 |            |                                                              | handle sign & handle the overflow of interger  |                                                              |                                                              |
| 0007  | [Revser Integer](https://leetcode.com/problems/reverse-integer/) | Easy       | 2020-11-12<br />12-23      |            |                                                              |                                                |                                                              |                                                              |
| 0013  | [Roman to Integer](https://leetcode.com/problems/roman-to-integer/) | Easy       | 2020-11-13<br />12-25      |            |                                                              |                                                |                                                              |                                                              |
| 0014  | [Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/) | Easy       | 2020-11-14<br />12-27      | 30mins.    |                                                              |                                                |                                                              |                                                              |
| 0028  | [Implement strStr()](https://leetcode.com/problems/implement-strstr/) | Easy       | 2020-11-14                 | 15mins.    |                                                              |                                                |                                                              |                                                              |
| 0031  | [Next Permutation](https://leetcode.com/problems/next-permutation/) | Medium     | 2020-11-15<br />12-30      | 2 hrs      |                                                              |                                                |                                                              |                                                              |
| 0058  | [Length of Last word](https://leetcode.com/problems/length-of-last-word/) | Easy       | 2020-11-16<br />2021-1-1   | 10mins.    |                                                              |                                                |                                                              |                                                              |
| 0067  | [Add Binary](https://leetcode.com/problems/add-binary/)      | Easy       | 2020-11-16<br />2021-1-3   | 2 hrs      |                                                              |                                                |                                                              | Refer. solution                                              |
| 0125  | [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/) | Easy       | 2020-11-19<br />2021-1-5   | 15mins     |                                                              |                                                |                                                              |                                                              |
| 0151  | [Reverse words in a String](https://leetcode.com/problems/reverse-words-in-a-string/) | Medium     | 2020-11-20<br />2021-1-7   | 43mins     |                                                              |                                                |                                                              |                                                              |
| 0165  | [Compare Version numbers](https://leetcode.com/problems/compare-version-numbers/) | Medium     | 2020-11-21<br />2021-1-8   | 62mins     |                                                              |                                                |                                                              |                                                              |
| 0344  | [Reverse String](https://leetcode.com/problems/reverse-string/) | Easy       | 2020-11-21<br />1-9        | 12mins     |                                                              |                                                |                                                              | in-place O(1)                                                |
| 0345  | [Reverse Vowels of a String](https://leetcode.com/problems/reverse-vowels-of-a-string/) | Easy       | 2020-11-22<br />1-10       | 32mins     |                                                              |                                                |                                                              |                                                              |
| 0387  | [First Unique character in a string](https://leetcode.com/problems/first-unique-character-in-a-string/submissions/) | Easy       | 2020-11-23                 | 36mins     |                                                              |                                                |                                                              | Refer.solution                                               |
| 0415  | [Add Strings](https://leetcode.com/problems/add-strings/)    | Easy       | 2020-11-24                 | 30mins     |                                                              |                                                |                                                              | (similar to 0067 add binary)                                 |
| 0443  | [String Compression](https://leetcode.com/problems/string-compression/) | Medium     | 2020-11-25                 | 1+ hr      |                                                              |                                                |                                                              | refer solution                                               |
| 0459  | [Repeated substring pattern](https://leetcode.com/problems/repeated-substring-pattern/) | Easy       | 2020-11-27                 | 23 mins    |                                                              |                                                |                                                              | refer solution (similar CTCI problem 1.9)                    |
| 0521  | [Longest uncommon subsequence I](https://leetcode.com/problems/longest-uncommon-subsequence-i/) | Easy       | 2020-11-29                 | 30mins     |                                                              |                                                |                                                              | refer solution                                               |
| 0541  | [Reverse String II](https://leetcode.com/problems/reverse-string-ii/) | Easy       | 2020-11-30                 | 35mins     |                                                              |                                                |                                                              |                                                              |
| 0557  | [Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/) | Easy       | 2020-12-1                  | 14mins     |                                                              |                                                |                                                              | brute force (memory usage could be improved)                 |
| 0680  | [Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/) | Easy       | 2020-12-1                  | 11mins     |                                                              |                                                |                                                              | Time limit exceed, need to find better solution. [refer to solution] |
| 0686  | [Repeated String match](https://leetcode.com/problems/repeated-string-match/) | Medium     | 2020-12-3                  | 43mins     |                                                              |                                                |                                                              | Passed with bad performance                                  |
| 0819  | [Most common words](https://leetcode.com/problems/most-common-word/) | Easy       | 2020-11-28                 | 30mins     |                                                              |                                                |                                                              | brute force solution                                         |
| 0824  | [Goat latin](https://leetcode.com/problems/goat-latin/)      | Easy       | 2020-12-5                  | 23mins     | Use of HashSet                                               |                                                | "Pig Latin"                                                  |                                                              |
| 0859* | [Buddy Strings](https://leetcode.com/problems/buddy-strings/) | Easy       | 2020-12-5                  | 67mins+    | 3 scenarios   [Tips below]                                   |                                                |                                                              | not sure where to start - refer to solution                  |
| 1081  | [Smallest subsequence of distinct characters](https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/) | Medium     | 2020-12-8                  |            | 1, smallest subsequence<br />2, contains all distinct <br />Use Stack | How to keep the order ?                        | [316](https://leetcode.com/problems/remove-duplicate-letters/) | refer to solution.                                           |
| 1169  | [Invalid transactions](https://leetcode.com/problems/invalid-transactions/) | Medium     | 2020-12-10                 | 50mins +   | hashMap + linkedList                                         |                                                |                                                              | eventually refer to solution                                 |
| 1309  | [Decrypt String from Alphabet to Integer Mapping](https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping/) | Easy       | 2020-12-14                 | 38mins     | Need know ASCII very well. <br />Need group the value range  |                                                |                                                              |                                                              |
| 1316  | [Distinct Echo Substrings](https://leetcode.com/problems/distinct-echo-substrings/) | Hard       | 2020-12-15                 | 22mins+    | Need figure out how to ger all substring comparsion faster   | Need write the hash function                   |                                                              | refer to solution                                            |
| 1324  | [Print words Vertically](https://leetcode.com/problems/print-words-vertically/submissions/) | Medium     | 2020-12-17                 | 21mins     |                                                              | How to remove only the trailing space          | Rotate matrix ?                                              | Performance need improved                                    |

**String** --> collection of character (array)

**String** related LeetCode Problems: 

https://github.com/liweiwei1419/LeetCode-Solutions-in-Good-Style/tree/master/string/Java



# Take away



## Primitive Data Types

| Data Type | Size    | Description                                                  |
| :-------- | :------ | :----------------------------------------------------------- |
| byte      | 1 byte  | Stores whole numbers from -128 to 127                        |
| short     | 2 bytes | Stores whole numbers from -32,768 to 32,767                  |
| int       | 4 bytes | Stores whole numbers from -2,147,483,648 to 2,147,483,647    |
| long      | 8 bytes | Stores whole numbers from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 |
| float     | 4 bytes | Stores fractional numbers. Sufficient for storing 6 to 7 decimal digits |
| double    | 8 bytes | Stores fractional numbers. Sufficient for storing 15 decimal digits |
| boolean   | 1 bit   | Stores true or false values                                  |
| char      | 2 bytes | Stores a single character/letter or ASCII values             |

- Java String is Immutable; 

  - e.g.  `test = test.replace("a", "b");`  //assign value back to `test`

- The **java.lang.Math.floor()** returns the double value that is less than or equal to the argument and is equal to the nearest mathematical integer.

- You can parse any number string to Int/long with difference radix ` Integer.parseInt(x, radix)`

  - e.g. `Integer.parseInt("1011", 2)` will parse the string as binary input value; 
  - Note: For Integer It only able to handle Positive numbers;

-  For parse super long string to number, try the two following methods: [ref](https://stackoverflow.com/questions/11860311/how-to-convert-binary-number-to-double-in-java)

  - #1 

    ```java
    public static double toDouble(byte[] bytes) {
         return ByteBuffer.wrap(bytes).getDouble();
    }
    ```

  - #2

    ```java
    String text = "1100000110011101010111011000101011011000011111111111111111111110";
    double doubleVal = Double.longBitsToDouble(new BigInteger(text, 2).longValue());
    System.out.println(doubleVal);
    ```

- How to Convert ASCII to String conversion Using Java ?

  - int a = 65;
  - Character.toString(a);
  - [bitwise operation](https://www.vojtechruzicka.com/bit-manipulation-java-bitwise-bit-shift-operations/);

- How to convett char array (char[]) to String ? [ref](https://beginnersbook.com/2014/06/how-to-convert-a-char-array-to-a-string-in-java/)

  - ```java
    char[] ch = {'g', 'o', 'o', 'd', ' ', 'm', 'o', 'r', 'n', 'i', 'n', 'g'};
    //#1 Using string object
    String str = new String(ch);
    
    //#2 Using valueOf method
    String str = String.valueOf(ch);
    ```

- How to clean StringBuilder ? [Answer](https://www.javacodeexamples.com/java-stringbuilder-clear-example-how-to-empty-stringbuilder-stringbuffer/1535)

  - `sb.setLength(0)` consider the best choice* 
  - `new StringBuilder()` object creation is costly -- not recommened, especially not in the loop.
  - `sb.delete(0,sb.length)` internally allocate new buffer, which is costly.

- How to check if a characer is Alphanumeric ?

  - ```java
    Character.isLetter(c) ||Character.isDigit(c)
    ```

- What's the different between **StringBuilder** and **StringBuffer** ? 

  - [`StringBuffer`](http://docs.oracle.com/javase/8/docs/api/java/lang/StringBuffer.html) is **synchronized**, [`StringBuilder`](http://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html) is not. (Similar to the differences betwee `Vector` and `ArrayList`)

- What's the different between `strip()` and `trim()`?

  - `strip()` is "Unicode-aware" evolution of `trim()`.

- How to increament HashMap<Character,Interger> count ? 

  - `map.put(key, map.getOrDefault(key,0) + 1);`

- How to get Numeric(int) value out of Char ? 

  - `Character.getNumericValue('1')` ==>  1 (int)

  - or Numeric(int) to char 

  - ```java
    int a=1;    
    char c=(char)(a+'0');
    ```

- How to remove element from Array ? 

  - #1, Using Two arrays;
  - #2, ArraysUtils.remove() from Apache Commons pacakge;
  - #3, Using for loop to shift element from the index that need be removed; 
  
- How to grab word out of string by using regex ? 

  - ```java
            Pattern p = Pattern.compile("[a-zA-Z]+");
            Matcher m = p.matcher(paragraph.toLowerCase());
          
            while (m.find()) {
                count.put(m.group(), count.getOrDefault(m.group(), 0) + 1);
                // System.out.println(m.group());
            }
    ```

- How to reverse String in Java ?

  - #1 StringBuilder/StringBuffer --> sb.reverse(); 
  - #2  Collections.reverse(charArray);
  - #3 Convert to Byte[] pr Char[] then loop through (good for in-place reverse to save memory);

- Java `subString(begin, end)`  method note.

  - **Parameters:**
    - **beginIndex** the beginning index, <u>inclusive</u>.
    - **endIndex** the ending index, <u>exclusive</u>.
  - e.g. "hamb**urge**r".substring(4, 8) returns "urge" 

- What is the difference between `CharSequence` and `String` ?

  - `CharSequence` --> interface;
    - Does not make any guarantees about whether the sequence is mutable or not. 
  - `String` --> implementing `CharSequence`; 
  - ![img](https://i.stack.imgur.com/PIFk9.png)
  
- How to count unique characters in String ? [ref](https://stackoverflow.com/questions/22597527/counting-unique-characters-in-a-string-given-by-the-user/22597587#22597587)

  - ```java
    public static long countUniqueCharacters(String input) {
        return input.chars()
                .distinct()
                .count();
    }
    ```

  - long to int ==> `Math.toIntExact(long)`; 
  
- Java ternary conditional operator

  - ```java
    boolean statement ? true result : false result;
    ```

  - e.g. `vowels.contains(w.charAt(0)) ? w : w.substring(1) + w.charAt(0)`

- How to swap character in String ? 

- What is **LinkedHashMap** ? 

  - It is the same as HashMap with an additional feature that it **maintains insertion order**. 
    - For example, when we run the code with a HashMap, we get a different order of elements.
  
- How to handle `java.util.ConcurrentModificationException` ? ([ref](https://www.journaldev.com/378/java-util-concurrentmodificationexception))

  - Essentially, the *ConcurrentModificationException* is used to **fail-fast when something we are iterating on is modified.** [[ref](https://www.baeldung.com/java-concurrentmodificationexception)]

  - Two options: [from [SOF](https://stackoverflow.com/a/8104702/3233111)] 

    - Create a list of values you wish to remove, *adding* to that list within the loop, then call `originalList.removeAll(valuesToRemove)` at the end

    - Use the `remove()` method on the iterator itself. Note that this means you can't use the enhanced for loop.

    - e.g. 

      ```java
      List<String> list = new ArrayList<String>();
      ...
      for (Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
          String value = iterator.next();
          if (value.length() > 5) {
              iterator.remove();
          }
      }
      ```
    
  - More about Iterator [here](https://www.journaldev.com/13460/java-iterator) 
  
- How to remove trailing whitespaces from String ([ref](https://howtodoinjava.com/java/string/trim-remove-trailing-spaces/))

  - #1 Method 

    ```java
    String regex = "\\s+$";
             
    String originalString1 = "howtodoinjava.com   ";    //3 trailing spaces
    String originalString2 = "   howtodoinjava.com   "; //3 leading and trailing spaces
     
    String trimmedString1 = originalString1.replaceAll(regex, "");
    String trimmedString2 = originalString2.replaceAll(regex, "");
     
    System.out.println(trimmedString1);
    System.out.println(trimmedString2);
    ```






# Problem Solutions/Tips

**ZigZag Conversion**:

Approach 2: Visit by Row (?)

**Intuition**

Visit the characters in the same order as reading the Zig-Zag pattern line by line.

**Algorithm**

Visit all characters in row 0 first, then row 1, then row 2, and so on...

For all whole numbers k*k*,

- Characters in row 00 are located at indexes k  (2⋅numRows−2)
- Characters in row numRows−1are located at indexes k  (2⋅numRows−2)+numRows−1
- Characters in inner row i*i* are located at indexes k  (2⋅numRows−2)+i and (k+1)(2⋅numRows−2)−i.



**00031-Next Permutation [Solution](https://leetcode.com/problems/next-permutation/solution/)**:

First, we observe that for any given sequence that is in descending order, no next larger permutation is possible. 

We need to find the first pair of two successive numbers a[i]*a*[*i*] and a[i-1]*a*[*i*−1], from the right, which satisfy a[i] > a[i-1]*a*[*i*]>*a*[*i*−1].

![ Next Permutation ](https://leetcode.com/media/original_images/31_nums_graph.png)

E.g. 158476531 -- Steps 

1. Start from right, find the first decreasing element --> 4 
2. start from element 4 to the right, find the number just large (closest) to 4 ---> 5
3. Swap 4 & 5 --> 158**5**76**4**31
4. Resort/Reverse everything from the right side of 5 --> 158513467 

![Next Permutation](https://leetcode.com/media/original_images/31_Next_Permutation.gif)



**Longest Uncommon Subsequence**

#1 brute force solution from the site 

```java
public class Solution {
    public int findLUSlength(String a, String b) {
        HashMap < String, Integer > map = new HashMap < > ();
        for (String s: new String[] {a, b}) {
            for (int i = 0; i < (1 << s.length()); i++) {
                String t = "";
                //Not quite understand the following 3 lines of code 
                for (int j = 0; j < s.length(); j++) {
                    if (((i >> j) & 1) != 0)
                        t += s.charAt(j);
                }
                if (map.containsKey(t))
                    map.put(t, map.get(t) + 1);
                else
                    map.put(t, 1);
            }
        }
        int res = -1;
        for (String s: map.keySet()) {
            if (map.get(s) == 1)
                res = Math.max(res, s.length());
        }
        return res;
    }
}
```

#2 Simple Solution

Simple analysis of this problem can lead to an easy solution.

These three cases are possible with string a*a* and b*b*:-

- a=b -->  return -1 
- Length(a) = length(b) -->either one 
- Length(a) != length(b) --> longer one 

```java
public class Solution {
    public int findLUSlength(String a, String b) {
        if (a.equals(b))
            return -1;
        return Math.max(a.length(), b.length());
    }
}
```



**BuddyStrings**

Solution: 

- If `A.length() != B.length()`: no possible swap
- If `A == B`, we need swap two same characters. Check is **duplicated char** in `A`. 
- As long as there is duplicate char in the string count[char] > 1 
- In other cases, we find index for `A[i] != B[i]`. There should be only 2 diffs and it's our one swap.



**SmallestSubsequenceofDistinctCharacters**

Solution:

- Find the index of last occurrence for each character.
- Use a `stack` to keep the characters for result.
- Loop on each character in the input string `S`,
- if the current character is smaller than the last character in the stack, and the last character exists in the following stream, we can pop the last character to get a smaller result.

