Strings

What is a String?

A String in Java is an immutable sequence of characters. Once created, it cannot be changed.

String s = "Hello";
// s is stored in the String Pool (special memory area)
// The characters 'H', 'e', 'l', 'l', 'o' cannot be modified

String Memory Layout

String s = "Hello";

String Pool:
+---+---+---+---+---+
| H | e | l | l | o |
+---+---+---+---+---+
  ↑
  s (reference)

Why Immutable?

1. Security: Strings are used for class loading, network connections
2. Thread Safety: Immutable objects are inherently thread-safe
3. String Pooling: Can reuse identical strings
4. Hashing: Hash code can be cached

String Declaration

// Literal (stored in String Pool)
String s1 = "Hello";

// New object (stored in heap)
String s2 = new String("Hello");

// They are equal in content but different objects
s1.equals(s2);    // true (content comparison)
s1 == s2;         // false (reference comparison)

Common Operations

String s = "Hello, World!";

// Length
int len = s.length();           // 13

// Access character
char c = s.charAt(0);          // 'H'

// Substring
String sub = s.substring(0, 5); // "Hello"
String sub2 = s.substring(7);   // "World!"

// Find index
int idx = s.indexOf('W');       // 7
int idx2 = s.indexOf("World");  // 7

// Case conversion
String upper = s.toUpperCase(); // "HELLO, WORLD!"
String lower = s.toLowerCase(); // "hello, world!"

// Trim whitespace
String padded = "  hello  ";
padded.trim();                  // "hello"

// Replace
String replaced = s.replace('o', '0'); // "Hell0, W0rld!"

// Split
String[] words = s.split(", "); // ["Hello", "World!"]

// Join
String joined = String.join("-", "a", "b", "c"); // "a-b-c"

// Starts/Ends with
boolean starts = s.startsWith("Hello"); // true
boolean ends = s.endsWith("!");         // true

Immutability Gotcha

// Each operation creates a NEW String
String s = "Hello";
s = s + " World";  // Creates new String "Hello World"
// Original "Hello" still exists in memory

// This is O(n) for concatenation!
for (int i = 0; i < 10000; i++) {
    s = s + "a";  // Very slow: O(n²) total
}

The Problem with String Concatenation

// BAD: O(n²) time
String result = "";
for (int i = 0; i < n; i++) {
    result += "a";  // Creates new String each time
}

The Solution: StringBuilder

// GOOD: O(n) time
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append("a");  // Modifies internal buffer
}
String result = sb.toString();

StringBuilder Operations

StringBuilder sb = new StringBuilder();

// Append
sb.append("Hello");
sb.append(' ');
sb.append(123);           // Auto-converts to string

// Insert
sb.insert(5, ",");        // "Hello, 123"

// Delete
sb.delete(5, 6);          // "Hello 123"
sb.deleteCharAt(0);       // "ello 123"

// Replace
sb.replace(0, 1, "H");    // "Hello 123"

// Reverse
sb.reverse();             // "321 olleH"

// Length
int len = sb.length();    // 9

// Convert to String
String result = sb.toString();

When to Use StringBuilder

Situation	Use
Single concatenation	String
Loop concatenation	StringBuilder
Building string character by character	StringBuilder
String is already final	String

Performance Comparison

// String: O(n²)
String s = "";
for (int i = 0; i < 100000; i++) {
    s += "a";  // Very slow
}

// StringBuilder: O(n)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 100000; i++) {
    sb.append("a");  // Very fast
}

For n=100,000:

• String: ~10 seconds
• StringBuilder: ~0.01 seconds

What is a Palindrome?

A string that reads the same forwards and backwards.

Examples:

• "racecar" → palindrome
• "hello" → not palindrome
• "A man a plan a canal Panama" → palindrome (ignoring spaces and case)

Basic Palindrome Check

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// Time: O(n), Space: O(1)

Valid Palindrome (LeetCode 125)

Consider only alphanumeric characters and ignore cases.

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;
}

Longest Palindromic Substring (LeetCode 5)

// Expand around center approach
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        // Check odd-length palindromes
        int len1 = expandAroundCenter(s, i, i);
        // Check even-length palindromes
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            start = i - (len - 1) / 2;
            maxLen = len;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}
// Time: O(n²), Space: O(1)

Palindrome Patterns

1. Two Pointers: Basic palindrome check
2. Expand Around Center: Find palindromic substrings
3. Dynamic Programming: Count palindromic substrings
4. Manacher's Algorithm: Find all palindromes in O(n)

What is an Anagram?

Two strings are anagrams if they contain the same characters with the same frequencies.

Examples:

• "listen" and "silent" → anagrams
• "hello" and "bello" → not anagrams

Check if Two Strings are Anagrams

Approach 1: Sorting

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    
    char[] sArr = s.toCharArray();
    char[] tArr = t.toCharArray();
    Arrays.sort(sArr);
    Arrays.sort(tArr);
    
    return Arrays.equals(sArr, tArr);
}
// Time: O(n log n), Space: O(n)

Approach 2: Character Count

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}
// Time: O(n), Space: O(1)

Group Anagrams (LeetCode 49)

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String sorted = new String(chars);
        
        map.computeIfAbsent(sorted, k -> new ArrayList<>()).add(str);
    }
    
    return new ArrayList<>(map.values());
}
// Time: O(n × k log k), Space: O(n × k)
// where n = number of strings, k = max string length

Find All Anagrams in a String (LeetCode 438)

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;
    
    int[] pCount = new int[26];
    int[] sCount = new int[26];
    
    for (int i = 0; i < p.length(); i++) {
        pCount[p.charAt(i) - 'a']++;
        sCount[s.charAt(i) - 'a']++;
    }
    
    if (Arrays.equals(pCount, sCount)) {
        result.add(0);
    }
    
    for (int i = p.length(); i < s.length(); i++) {
        sCount[s.charAt(i) - 'a']++;
        sCount[s.charAt(i - p.length()) - 'a']--;
        
        if (Arrays.equals(pCount, sCount)) {
            result.add(i - p.length() + 1);
        }
    }
    
    return result;
}
// Time: O(n), Space: O(1)

Anagram Patterns

1. Sorting: Simple but O(n log n)
2. Character Count: Optimal O(n)
3. Sliding Window: For finding anagram substrings

Naive Approach

// Search for pattern in text
int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        int j = 0;
        while (j < needle.length() && haystack.charAt(i + j) == needle.charAt(j)) {
            j++;
        }
        if (j == needle.length()) return i;
    }
    return -1;
}
// Time: O(n × m), Space: O(1)

KMP Algorithm (Knuth-Morris-Pratt)

KMP avoids redundant comparisons by using information from previous matches.

public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    
    int[] lps = buildLPS(needle);
    int i = 0, j = 0;
    
    while (i < haystack.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
            if (j == needle.length()) {
                return i - j;
            }
        } else {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

private int[] buildLPS(String pattern) {
    int[] lps = new int[pattern.length()];
    int len = 0;
    int i = 1;
    
    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}
// Time: O(n + m), Space: O(m)

Rabin-Karp (Rolling Hash)

public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    
    int n = haystack.length();
    int m = needle.length();
    int base = 256;
    int mod = 101;
    
    int needleHash = 0;
    int windowHash = 0;
    int basePowM = 1;
    
    // Precompute base^(m-1) % mod
    for (int i = 0; i < m - 1; i++) {
        basePowM = (basePowM * base) % mod;
    }
    
    // Compute initial hashes
    for (int i = 0; i < m; i++) {
        needleHash = (needleHash * base + needle.charAt(i)) % mod;
        windowHash = (windowHash * base + haystack.charAt(i)) % mod;
    }
    
    // Slide the window
    for (int i = 0; i <= n - m; i++) {
        if (needleHash == windowHash) {
            // Verify match
            if (haystack.substring(i, i + m).equals(needle)) {
                return i;
            }
        }
        
        if (i < n - m) {
            windowHash = (windowHash - haystack.charAt(i) * basePowM) * base + haystack.charAt(i + m);
            windowHash = ((windowHash % mod) + mod) % mod;
        }
    }
    return -1;
}
// Time: O(n + m) average, Space: O(1)

When to Use Each

Algorithm	Time	Space	Best For
Naive	O(nm)	O(1)	Small texts
KMP	O(n+m)	O(m)	Single pattern
Rabin-Karp	O(n+m)	O(1)	Multiple patterns