String.md

String

• Concept
• Strategies
• Common topics

Concept

• Substring
  • A substring is a contiguous non-empty sequence of characters within a string.
• Subsequence
  • A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
• Anagrams
  • An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
• Shifting
  • Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a').
  • Shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Strategies

• Parentheses
  • Possible solutions for solving parentheses problems:
    • Stack
      • Basic logic
        • Meet (, push the index into stack.
        • Meet ), pop the index of the corresponding ( from stack.
      • Template

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {               // meet (
                stack.push(i);
            } else if (s.charAt(i) == ')') {        // meet )
                if (!stk.isEmpty()) {
                    int leftIndex = stack.pop();
                } else {                            // if there is no corresponding (
                }
            } else {                                // meet other characters except parenthese
                
            }
        }

      • Notes
        • Push the index rather than pushing the actual parenthese into the stack.
    • Counter
      • Basic logic
        • Meet (, counter increased by 1;
        • Meet ), counter decreased by 0;
• Group string array
  • Find a encoding logic, which 2 strings should be grouped together will have the same encoding value.
• Palindrome
  • Possible solutions for solving parentheses problems:
    • Stack
    • 2 Pointers (Meet pointers)
      • Template

        boolean isPalindrome(String s, int left, int right) {
            while (left < right) {
                if (s.charAt(left) != s.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

  • Note
    • Need to consider 2 possible cases: length of palindrome is even or odd.
      • Example of even length palindrome: abccba
      • Example of odd length palindrome: abcxcba
      • Example problems for considering those 2 possible cases
        • Longest Palindromic Substring
        • Is Palindrome List

Common topics

back to Problem_Categories

• Check characteristics
  • Symmetric
    • Parentheses
      • Is Valid Parentheses
      • Generate All Combinations of Parentheses
      • Remove Minimum Parentheses to Make Parentheses Valid
      • Get All Possible Strings by Removing Minimum Number of Invalid Parentheses
      • Score of Parentheses
      • Longest Valid Parentheses Substring
    • Palindrome
      • Is Palindrome String
      • Is Palindrome String by Removing One Char
      • Is Palindrome String by Only Considering Alphanumeric Characters
      • Can Characters of String Form Palindrome
      • Longest Palindromic Substring
      • Palindrome Partitioning
      • 132 Palindrome Partitioning II
      • 1278 Palindrome Partitioning III
      • 1745 Palindrome Partitioning IV
• Substring
  • Single string
    • Count Binary Substrings
    • Longest Palindromic Substring
    • Longest Valid Parentheses Substring
    • Longest Substring Without Repeating Characters
    • Longest Substring of Repeating Character by Replacement
  • 2 strings
    • Shortest Substring Has Every Character From Another String
    • Does First String Has Substring Which Is Permutation Of Second String
    • Find All Anagrams in a String
• Strings comparison
  • Subsequences
    • Distinct Subsequences
    • 1143 Longest Common Subsequence
  • Substring
    • Shortest Substring Has Every Character From Another String
    • Does First String Has Substring Which Is Permutation Of Second String
    • Find All Anagrams in a String
  • Edit Distance
  • 14 Longest Common Prefix
• Math
  • Get All Operator Combinations to Make Expression Match Target Number
  • Basic calculator
    • 224 Basic Calculator
    • 227 Basic Calculator II
    • Basic Calculator III
    • 770 Basic Calculator IV
  • Add
    • 67 Add Binary
    • 415 Add Strings
• Combinations
  • Get All Operator Combinations to Make Expression Match Target Number
• Sorting in custom order
  • Ancestral Names
  • Get Lexicographically Increasing Order from Words (Alien Dictionary)
• Conversion (Decoding and encoding)
  • Decoding
    • Decode String
    • Decode Ways
  • Roman numerals
    • Ancestral Names
    • 12 Integer to Roman
    • 13 Roman to Integer
  • Other
    • Convert Integer to English Words
    • Valid Word Abbreviation
• Manipulation
  • Remove
    • Remove K Digits to Make Smallest Integer
  • Rearrange
    • Reorganize String for Two Adjacent Characters Are Not Same
  • Split
    • Word Break (Return boolean - Check the string can be broken by words or not)
    • Word Break II (Return list - Get all the possible word breaking combinations)
    • Palindrome Partitioning
    • Restore IP Addresses
  • Rotate
    • 796 Rotate String
  • Shift
    • Shifting Letters
  • Merge
    • Merge Strings Alternately
• Input is string array
  • Grouping string array (See strategies section)
    • Group Shifted Strings
    • Group Anagrams
  • Longest String Chain
  • 14 Longest Common Prefix
• Other
  • Case in real life
    • Convert Absolute Path to Canonical Path
    • Reformat Date
  • Stars and Bars
  • Greatest Common Divisor of Strings

back to Problem_Categories