String Basics & Manipulation

1. Introduction: The Immutable Chain

Strings are arguably the most common data type you will manipulate in software engineering. Everything from reading a JSON payload, to parsing a URL, to formatting a user's name involves String manipulation.

However, in Java (and many other languages like Python and C#), Strings have a massive, fundamental restriction: They are Immutable. Once a String object is created in memory, its characters can never be changed. If you try to modify a string (e.g., s = s + "a"), Java secretly creates a brand new String object in memory, copies the old characters over, adds the new character, and throws the old object in the trash.

If you don't understand Immutability and ASCII math, string manipulation in technical interviews will result in catastrophic $O(N^2)$ time complexities and memory limit exceptions.

2. Core Concept: StringBuilder & Character Math

The StringBuilder

Because appending to a String takes $O(N)$ time (copying the whole string), doing it inside a loop of size $N$ takes $O(N^2)$ time. To build or modify strings dynamically, you MUST use StringBuilder. It uses a resizable char[] array under the hood, allowing $O(1)$ amortized appends.

ASCII Math

Characters in Java are just integers under the hood, representing their ASCII values.

• 'a' is 97, 'b' is 98 ... 'z' is 122.
• 'A' is 65.
• '0' is 48.

You can do math on them!

• char c = 'd'; int index = c - 'a'; (Yields 3).
• char numChar = '7'; int val = numChar - '0'; (Yields the integer 7).
• char upper = (char)(c - 32); (Converts 'd' to 'D').

3. Beginner Code Example: String Reversal & Rebuilding

Problem Statement: (LeetCode 344) Reverse a string array in place. (Alternatively, reverse a standard String object).

If given a char[], we can swap in place ($O(1)$ space). If given a String, we must use StringBuilder ($O(N)$ space).

public class StringReversal {
    
    // In-place reversal for char arrays
    public void reverseCharArray(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
    
    // Reversal for immutable String objects
    public String reverseStringObject(String s) {
        // ALWAYS use StringBuilder for modifications
        StringBuilder sb = new StringBuilder(s);
        
        // StringBuilder has a built-in reverse!
        sb.reverse();
        
        return sb.toString();
    }
}

4. Intermediate Code Example: String to Integer (atoi)

Problem Statement: (LeetCode 8) Implement myAtoi(string s), which converts a string to a 32-bit signed integer. It must handle leading whitespaces, optional + or - signs, and stop reading when it hits a non-digit character. It must also clamp the value if it exceeds the 32-bit integer limits.

The Insight: This tests your ability to parse characters safely without throwing Exceptions, and tests your understanding of Integer overflow math.

public class StringToInteger {
    public int myAtoi(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int i = 0;
        int n = s.length();
        int sign = 1;
        int result = 0;
        
        // 1. Skip leading whitespaces
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        
        // Edge case: string was entirely spaces
        if (i == n) return 0;
        
        // 2. Check for optional sign
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }
        
        // 3. Process digits
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0'; // ASCII math!
            
            // 4. Check for Overflow BEFORE adding the digit
            // Integer.MAX_VALUE is 2147483647.
            // If our result is already > 214748364, multiplying by 10 will overflow.
            // If it equals 214748364, multiplying by 10 makes 2147483640. Adding a digit > 7 overflows!
            if (result > Integer.MAX_VALUE / 10 || 
               (result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            // Push the digit onto our number (e.g., 45 * 10 + 2 = 452)
            result = result * 10 + digit;
            i++;
        }
        
        return result * sign;
    }
}

5. Advanced Code Example: Longest Common Prefix

Problem Statement: (LeetCode 14) Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". (e.g., ["flower","flow","flight"] -> "fl").

The Horizontal Scanning Insight: Start by assuming the first string is the longest common prefix. Then compare it against the second string, chopping letters off the end of your prefix until it matches. Repeat for all strings.

public class LongestPrefix {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        // Start by assuming the entire first string is the prefix
        String prefix = strs[0];
        
        for (int i = 1; i < strs.length; i++) {
            // .indexOf returns 0 if the string starts with the prefix.
            // If it returns -1 (not found) or > 0 (found later in the string), it's not a true prefix!
            while (strs[i].indexOf(prefix) != 0) {
                // Chop one character off the end of the prefix and try again
                prefix = prefix.substring(0, prefix.length() - 1);
                
                // If we chopped everything off, there is no common prefix
                if (prefix.isEmpty()) return "";
            }
        }
        
        return prefix;
    }
}

Complexity Analysis:

• Time Complexity: $O(S)$ where $S$ is the sum of all characters in all strings.
• Space Complexity: $O(1)$.

6. Common Mistakes Beginners Make

1. Using + or += in a loop

   • The Mistake: for(char c : arr) { str += c; }
   • Why it's wrong: Recreates a new String object every iteration. Memory usage skyrockets and execution time degrades to $O(N^2)$.
   • The Fix: StringBuilder sb = new StringBuilder(); for(char c : arr) { sb.append(c); } return sb.toString();

2. Using == to compare Strings

   • The Mistake: if (str == "test")
   • Why it's wrong: Java uses a "String Pool". Sometimes == works if both strings are literals. But if one string was generated via StringBuilder or substring, they reside at different memory addresses, and == returns false.
   • The Fix: ALWAYS use str.equals("test").

3. Calling .split("") to convert String to Array

   • The Mistake: String[] arr = s.split("");
   • Why it's wrong: Generates an array of String objects. This takes $O(N)$ time, but the Regex compilation inside split is very slow, and allocating thousands of 1-character String objects destroys memory.
   • The Fix: Use char[] arr = s.toCharArray(); for blazing fast primitive character manipulation.

7. Interview Q&A

Q1: What is the String Pool? Answer: To save memory, Java maintains a special area in the Heap called the String Constant Pool. If you write String a = "hello"; String b = "hello";, Java only creates one object. Both a and b point to the same memory address! This is why Strings MUST be immutable. If a changed its value to "jello", b would magically change too, which would cause chaos.

Q2: When should I use StringBuffer instead of StringBuilder? Answer: Almost never in interviews. StringBuffer is the thread-safe, synchronized version of StringBuilder. The synchronization locks make it slower. Unless you are explicitly writing multi-threaded concurrent code, stick to StringBuilder.

8. Practice Problems

1. Reverse String (LeetCode 344)
   • Goal: Two-pointer swapping on a char[].
2. String to Integer (atoi) (LeetCode 8)
   • Goal: Master ASCII math (c - '0') and manual overflow boundary checks.
3. Longest Common Prefix (LeetCode 14)
   • Goal: Master the indexOf shrinking loop.

9. Summary

• Immutability: Strings cannot be changed. Use StringBuilder to modify strings dynamically.
• ASCII Math: You can treat characters like integers. char - 'a' gives 0-25. char - '0' gives 0-9.
• Comparisons: Never use ==. Use .equals().
• Primitives over Objects: Prefer s.charAt(i) and s.toCharArray() over Regex and split().