Strings

In simple words

A string is a sequence of characters. In Java, String is immutable — every "change" creates a new object. For building strings use StringBuilder; for checking characters use char[] or charAt.

Key ideas

• Count letters with int[26] and c - 'a' — faster and simpler than a HashMap.
• Palindrome: two pointers from both ends moving inward.
• Anagram: same letter counts. Group anagrams by their sorted form or their count signature.
• Useful helpers: Character.isLetterOrDigit, Character.toLowerCase, String.join, s.split("\\s+").
• Expand-around-center finds the longest palindromic substring in O(n²) with O(1) space.
• Many string problems are really sliding window, hashing, or DP problems in disguise.

Operations & cost

Java code

// Valid palindrome, ignoring non-alphanumeric characters
boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
        while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
        if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
            return false;
        i++; j--;
    }
    return true;
}

// Anagram check with a count array
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;
}

// Longest palindromic substring: expand around each center
String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int c = 0; c < s.length(); c++) {
        int len = Math.max(expand(s, c, c), expand(s, c, c + 1));
        if (len > end - start) { start = c - (len - 1) / 2; end = c + len / 2; }
    }
    return s.substring(start, end + 1);
}
int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

Interview traps to remember

• Immutable: s.toUpperCase(); alone does nothing to s. Write s = s.toUpperCase();
• == vs equals: new String("hi") == "hi" is false. Always compare values with equals.
• Loops: s += x in a loop is O(n²). In our test, 100,000 appends took about 1.2 s with + and under 1 ms with StringBuilder.
• Chars are numbers: 'a' + 'b' is 195, so 'a' + 'b' + "c" prints 195c.
• Left to right: 1 + 2 + "3" is "33", but "1" + 2 + 3 is "123".
• split uses regex: "a.b".split(".") is an empty array. Write split("\\."). Trailing empty strings are dropped too.

Spot it when

• 'Anagram', 'palindrome', 'substring', 'character frequency'.

Practice problems

Interview tip

★ Clarify the character set first: only lowercase English letters? Upper case? Unicode? It decides between int[26], int[128] and a HashMap.