Chapter 6: String Algorithm From Elements of Programming Interviews

 Run Length Encoding
   static String decoding(String s) {
    int count = 0;
    StringBuilder ret = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (Character.isDigit(c)) {
        count = count * 10 + c - '0';
      } else { // isalpha.
        for (int i = 1; i <= count; i++) {
          ret.append(c);
        }
        count = 0;
      }
    }
    return ret.toString();
  }

  static String encoding(String s) {
    int count = 1;
    StringBuilder ss = new StringBuilder();
    for (int i = 1; i < s.length(); ++i) {
      if (s.charAt(i) == s.charAt(i - 1)) {
        ++count;
      } else {
        ss.append(count);
        ss.append(s.charAt(i - 1));
        count = 1;
      }
    }
    ss.append(count);
    ss.append(s.charAt(s.length() - 1));
    return ss.toString();
  }
Remove b and Replace b with dd
Main idea is to process backward
   static String replaceAndRemove(String s) {
    char[] sChars = s.toCharArray();
    // Removes "b" and count the number of "a".
    int writeIdx = 0, aCount = 0;
    for (char c : sChars) {
      if (c != 'b') {
        sChars[writeIdx++] = c;
      }
      if (c == 'a') {
        ++aCount;
      }
    }

    // Allocates space according to the number of "a".
    sChars = Arrays.copyOf(sChars, writeIdx + aCount);
    // Replace "a" with "dd".
    int curIdx = writeIdx - 1;
    writeIdx = sChars.length - 1;
    while (curIdx >= 0) {
      if (sChars[curIdx] == 'a') {
        sChars[writeIdx--] = 'd';
        sChars[writeIdx--] = 'd';
      } else {
        sChars[writeIdx--] = sChars[curIdx];
      }
      --curIdx;
    }
    return new String(sChars);
  }
PhoneMnemonic
  static void phoneMnemonicHelper(String num, int d, char[] ans) {
    if (d == num.length()) { // get enough characters and output answer.
      System.out.println(ans);
    } else {
      for (char c : M[num.charAt(d) - '0'].toCharArray()) { // try all
                                                            // combinations.
        ans[d] = c;
        phoneMnemonicHelper(num, d + 1, ans);
      }
    }
  }

  static void phoneMnemonic(String num) {
    char[] ans = new char[num.length()];
    phoneMnemonicHelper(num, 0, ans);
  }