2. Strings

Note

Why this matters for DSA Strings appear in ~30% of DSA problems (palindromes, anagrams, substring searches). Because Java strings are immutable, inefficient string concatenation is one of the most common causes of Time Limit Exceeded (TLE) in online judges. Mastering StringBuilder is an absolute requirement.

2.1 Creating & Immutability

In Java, a String is an object that represents a sequence of characters. Strings are immutable — once created, their values cannot be changed.

java

String s = "hello";
char first = s.charAt(0); // 'h' (0-indexed access)
int length = s.length();  // 5 (note: it's a method length(), unlike array.length)

// s.charAt(0) = 'H'; // ❌ Error! Cannot modify characters in place.

Tip

String ↔ char Array Conversion Since strings are immutable, modifying a character in place requires converting the string to a character array, making the changes, and converting it back:

java

String s = "hello";
char[] chars = s.toCharArray(); // ['h', 'e', 'l', 'l', 'o']
chars[0] = 'H';
s = new String(chars);          // "Hello"

2.2 StringBuilder (Efficient Concatenation)

Because strings are immutable, joining strings with + inside a loop creates a new string object every time. This takes $O(N^2)$ time.

java

// ❌ BAD PATTERN: O(N^2) time complexity
String s = "";
for (int i = 0; i < 10000; i++) {
    s += i; // Recreates a new String every iteration! Very slow.
}

java

// ✅ GOOD PATTERN: O(N) time complexity
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
    sb.append(i); // Appends internally to a mutable character array.
}
String s = sb.toString(); // Converted back to string at the end.

Essential StringBuilder Methods

java

StringBuilder sb = new StringBuilder("hello");
sb.append(" world");  // "hello world"
sb.insert(5, "!");    // "hello! world"
sb.deleteCharAt(5);   // "hello world"
sb.setCharAt(0, 'H'); // "Hello world" - O(1) in-place modification
sb.reverse();         // "dlrow olleH" - Reverses in place!
sb.length();          // 11
sb.setLength(0);      // Clears the builder (resets length to 0)

2.3 Useful String Methods

Java has a rich set of built-in methods for strings:

java

String s = "  Hello World!  ";

s.toLowerCase();                 // "  hello world!  "
s.toUpperCase();                 // "  HELLO WORLD!  "
s.trim();                        // "Hello World!" (removes leading/trailing spaces)
s.substring(1, 4);               // " He" (start: inclusive, end: exclusive)
s.substring(5);                  // "o World!  " (start to end)

// Search
s.indexOf('o');                  // 7 (first occurrence)
s.lastIndexOf('o');              // 10 (last occurrence)
s.contains("World");             // true

// Replace
s.replace("World", "Java");      // "  Hello Java!  "
s.replaceAll("\\s+", "");        // "HelloWorld!" (regex replace)

// Compare
String s1 = "hello";
String s2 = "hello";
String s3 = new String("hello");

s1.equals(s3);                   // true  (Double checks content - always use for strings)
s1 == s3;                        // false (Compares reference/memory address)
s1.compareTo("world");           // Returns negative (s1 is lexicographically smaller)

Warning

Never compare Strings with == In Java, == compares whether the objects refer to the same memory location, not their text values. Always use .equals() to check if two strings have the same content.

2.4 Splitting & Joining

Converting sentences into word lists and vice versa is another common DSA pattern.

java

// Splitting
String sentence = "hello world java";
String[] words = sentence.split(" "); // ["hello", "world", "java"]

// Joining
String joined = String.join("-", words); // "hello-world-java"

2.5 Character & ASCII Operations

In Java, chars are 16-bit Unicode characters. Since characters are represented by ASCII numbers internally, you can perform integer arithmetic on them.

java

// ASCII Conversions
char c = 'a';
int asciiVal = (int) c;   // 97
char charVal = (char) 97; // 'a'

// Check character properties via Character class
Character.isLetter('a');       // true
Character.isDigit('5');        // true
Character.isLetterOrDigit('!');// false
Character.isLowerCase('A');    // false
Character.isWhitespace(' ');   // true

Tip

Common DSA Pattern: Mapping characters to 0-25 If you are tracking lowercase English alphabet characters in a frequency array (hash table), subtract 'a' to get their 0-indexed position:

java

char c = 'c';
int index = c - 'a'; // 2 (since 'c' is 99 and 'a' is 97)

Practice Drill

java

// Try implementing these:
// 1. Reverse a given string using StringBuilder.
// 2. Check if a string is a palindrome (ignores case and non-alphanumeric chars).
// 3. Count the frequency of lowercase letters in a string and store it in an integer array of size 26.
// 4. Given a string, remove all vowels ('a', 'e', 'i', 'o', 'u', case-insensitive).

💡 Click for Solutions

java

public class StringDrill {
    public static void main(String[] args) {
        // 1. Reverse a string
        String s = "hello";
        String reversed = new StringBuilder(s).reverse().toString();
        System.out.println("Reversed: " + reversed); // "olleh"

        // 2. Palindrome check
        String pal = "RaceCar";
        boolean isPalindrome = checkPalindrome(pal);
        System.out.println("Is Palindrome: " + isPalindrome); // true

        // 3. Frequency count
        String text = "leetcode";
        int[] freq = new int[26];
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch >= 'a' && ch <= 'z') {
                freq[ch - 'a']++;
            }
        }
        System.out.println("Frequency of 'e': " + freq['e' - 'a']); // 3

        // 4. Remove vowels
        String original = "Hello World Java";
        StringBuilder noVowels = new StringBuilder();
        String vowels = "aeiouAEIOU";
        for (int i = 0; i < original.length(); i++) {
            char ch = original.charAt(i);
            if (vowels.indexOf(ch) == -1) {
                noVowels.append(ch);
            }
        }
        System.out.println("Without Vowels: " + noVowels.toString()); // "Hll Wrld Jv"
    }

    public static boolean checkPalindrome(String str) {
        String clean = str.toLowerCase();
        int left = 0;
        int right = clean.length() - 1;
        while (left < right) {
            if (clean.charAt(left) != clean.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

← Basics | Next → Control Flow