String fundamentals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

                 JVM HEAP MEMORY
+-------------------------------------------------------------+
|                                                             |
|   String s1 = "cat";                                        |
|   String s2 = "cat";                                        |
|                                                             |
|   +-----------------------------------------------------+   |
|   |                 STRING CONSTANT POOL                |   |
|   |                                                     |   |
|   |   [ Address: 0x100 | Value: "cat" ]                 |   |
|   |           ^                     ^                   |   |
|   |           |                     |                   |   |
|   |     s1 points here        s2 reuses same memory!    |   |
|   +-----------------------------------------------------+   |
|                                                             |
|   String s3 = new String("cat");                            |
|   [ Address: 0x240 | Value: "cat" (Separate Heap Object) ]  |
|           ^                                                 |
|     s3 points here                                          |
+-------------------------------------------------------------+

1
2
3
4
5
6
7
8
9
10
11
12

Naive Concatenation in a Loop:
Iteration 1: "" + 'a'      -> Allocates new String "a"       (copies 1 char)
Iteration 2: "a" + 'b'     -> Allocates new String "ab"      (copies 2 chars)
Iteration 3: "ab" + 'c'    -> Allocates new String "abc"     (copies 3 chars)
Iteration 4: "abc" + 'd'   -> Allocates new String "abcd"    (copies 4 chars)
...
Total Characters Copied: 1 + 2 + 3 + ... + n = O(n²) Time & massive GC pressure!

Optimal StringBuilder Approach:
Internal Buffer: [ 'a' | 'b' | 'c' | 'd' | _ | _ | _ | _ ]  (Capacity: 16)
Appends write directly into the next free index in O(1) amortized time!
Total Time for n appends: O(n)

1
2
3
4
5
6
7
8
9
10
11
12

// SLOW: O(n^2) - Creates n intermediate string objects in memory!
String result = "";
for (int i = 0; i < n; i++) {
    result += s.charAt(i); // Allocates a brand new copy every iteration
}

// FAST: O(n) - Uses an expandable backing array with amortized O(1) appends
StringBuilder sb = new StringBuilder(n);
for (int i = 0; i < n; i++) {
    sb.append(s.charAt(i)); // Appends in-place
}
String finalResult = sb.toString();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// PATTERN 1: Two Pointers (Inward Convergence for Palindromes) - O(n) time, O(1) space
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// PATTERN 2: Frequency Array (Anagram Verification) - O(n) time, O(1) space
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] counts = new int[26]; // Fixed size 26 for lowercase English letters
    for (int i = 0; i < s.length(); i++) {
        counts[s.charAt(i) - 'a']++;
        counts[t.charAt(i) - 'a']--;
    }
    for (int count : counts) {
        if (count != 0) return false;
    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Original String: " a   b   c   d   e "
Indices:           0   1   2   3   4

1. SUBSTRING (Strictly Contiguous):
   - Valid:   "bcd"  (indices 1..3 unbroken)
   - Valid:   "ab", "cde", "a"
   - Invalid: "ace"  (not contiguous!)
   - Formula: A string of length n has exactly n*(n + 1)/2 non-empty substrings.

2. SUBSEQUENCE (Order-Preserving, Non-Contiguous Allowed):
   - Valid:   "ace"  (delete 'b' and 'd', remaining order intact)
   - Valid:   "be", "acd", "abcde"
   - Invalid: "ca"   (violates relative ordering: 'c' appears after 'a')
   - Formula: A string of length n has 2^n total subsequences (including empty).

3. PREFIX & SUFFIX:
   - Prefix: Substring starting strictly at index 0 (e.g., "", "a", "ab", "abc")
   - Suffix: Substring ending strictly at index n-1 (e.g., "e", "de", "cde", "abcde")

1
2
3
4
5
6
7
8
9
10
11

s1 = "waterbottle"
s2 = "erbottlewat"

Concatenate s1 with itself:
s1 + s1 = "wat[erbottlewat]erbottle"
                ^          ^
                s2 is found as a substring!

Why this works:
Every possible cyclic rotation of s1 starts at some index i and wraps around.
In s1 + s1, the wrap-around simply continues into the second copy of s1!

1
2
3
4
5
6
7
8
9

public boolean isRotation(String s1, String s2) {
    // Both strings must be non-null and equal length
    if (s1 == null || s2 == null || s1.length() != s2.length()) {
        return false;
    }
    // (s1 + s1) contains every valid cyclic rotation of s1
    String doubled = s1 + s1;
    return doubled.contains(s2);
}