DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Mutable vs Immutable Strings

The Core Distinction

Immutable means once a string object is created, its content cannot change. Every "modification" — appending, replacing, upper-casing — creates a brand new string object in memory. The original is untouched.

Mutable means the string's content can be changed in place. Characters can be overwritten, new characters can be inserted, and the same object is modified without allocating a new one.

This distinction is not just academic. It determines whether a loop that builds a string runs in O(n) or O(n²). It determines whether you can modify a character at a specific index. It determines which APIs are available and what the thread-safety guarantees are.

Immutability in action:

  s = "hello"               ← creates object A at address 1000
  s = s + " world"          ← creates object B at address 2000
                               ("hello world" — 11 chars copied)
  s = s.toUpperCase()       ← creates object C at address 3000
                               ("HELLO WORLD" — 11 chars copied)

  Object A: "hello"         ← still in memory until garbage collected
  Object B: "hello world"   ← still in memory until garbage collected
  Object C: "HELLO WORLD"   ← current value of s

  Three allocations, three copies, just to get "HELLO WORLD".
  With n such operations: O(n²) total characters copied.

Language Summary

Language	Default String	Mutable Alternative	Notes
Java	`String` — immutable	`StringBuilder` (single-threaded), `StringBuffer` (thread-safe)	Always use StringBuilder in interviews
Python	`str` — immutable	`list` of chars, then `"".join()`	No dedicated mutable string class
C++	`std::string` — mutable	Already mutable — no alternative needed	Can modify chars directly
JavaScript	`string` — immutable primitive	`Array` of chars, then `.join("")`	Same pattern as Python

C++ is the outlier. std::string is directly mutable — you can write s[0] = 'H' and it works. Every other major language treats strings as immutable and provides a separate mutable buffer for building strings efficiently.

Java: String vs StringBuilder

String is immutable. StringBuilder is a mutable character buffer. This difference shows up constantly in interviews.

Java

public class StringVsStringBuilder {

    // Demonstrates the fundamental API difference
    public static void main(String[] args) {
        // --- Immutable String ---
        String s = "Hello";

        // Every method returns a NEW String — original unchanged
        String upper = s.toUpperCase();
        String appended = s + " World";
        String replaced = s.replace("l", "L");

        System.out.println("Original s:    " + s);        // "Hello" — unchanged
        System.out.println("upper:         " + upper);    // "HELLO"
        System.out.println("appended:      " + appended); // "Hello World"
        System.out.println("replaced:      " + replaced); // "HeLLo"

        // --- Mutable StringBuilder ---
        StringBuilder sb = new StringBuilder("Hello");

        // Every method modifies the SAME object — no new allocation
        sb.append(" World");           // Modifies sb in place
        sb.insert(5, ",");             // Insert at index 5
        sb.delete(0, 6);              // Delete characters 0-5
        sb.replace(0, 5, "Java");     // Replace range
        sb.reverse();                  // Reverse in place

        System.out.println("After operations: " + sb.toString()); // "avaJ"

        // StringBuilder useful methods
        StringBuilder builder = new StringBuilder();
        builder.append("one");
        builder.append(", ");
        builder.append("two");
        builder.append(", ");
        builder.append("three");

        System.out.println("Built string: " + builder.toString());
        System.out.println("Length: " + builder.length());
        System.out.println("charAt(0): " + builder.charAt(0));

        // Modify a character at a specific index — impossible with String
        builder.setCharAt(0, 'O');
        System.out.println("After setCharAt: " + builder.toString());
    }
}

Output (Java):
Original s:    Hello
upper:         HELLO
appended:      Hello World
replaced:      HeLLo
After operations: avaJ
Built string: one, two, three
After setCharAt: One, two, three

The O(n²) Trap and How to Avoid It

This is the most tested practical consequence of immutability. Building a string by concatenation in a loop is one of the most common interview anti-patterns.

Java

public class ConcatTrap {

    // BAD: O(n²) — creates a new String at every iteration
    public static String buildSlow(int n) {
        String result = "";
        for (int i = 0; i < n; i++) {
            result += (char)('a' + i % 26); // NEW String object every time
        }
        return result;
    }

    // GOOD: O(n) — appends to the same internal buffer
    public static String buildFast(int n) {
        StringBuilder sb = new StringBuilder(n); // Pre-size for zero resizes
        for (int i = 0; i < n; i++) {
            sb.append((char)('a' + i % 26));     // In-place append
        }
        return sb.toString();
    }

    // ALSO BAD (subtle): String.format inside a loop
    public static String buildFormat(int n) {
        String result = "";
        for (int i = 0; i < n; i++) {
            result += String.format("%c", 'a' + i % 26); // New String every time
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 100_000;

        long t1 = System.nanoTime();
        String slow = buildSlow(n);
        long time1 = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        String fast = buildFast(n);
        long time2 = (System.nanoTime() - t2) / 1_000_000;

        System.out.println("Slow (String +): " + time1 + " ms, length=" + slow.length());
        System.out.println("Fast (StringBuilder): " + time2 + " ms, length=" + fast.length());
        System.out.println("Speedup: ~" + (time1 / Math.max(time2, 1)) + "x");
    }
}

Output (approximate):
Slow (String +):      3200 ms  length=100000
Fast (StringBuilder):    2 ms  length=100000
Speedup: ~1600x

Modifying a Character at a Specific Index

Immutable strings make single-character modification non-trivial. This is a frequent interview requirement — change s[3] to a different character.

Java

public class ModifyCharAtIndex {

    // Method 1: StringBuilder — most efficient for multiple modifications
    public static String replaceCharSB(String s, int index, char newChar) {
        StringBuilder sb = new StringBuilder(s);
        sb.setCharAt(index, newChar);     // O(1) — direct index write
        return sb.toString();             // O(n) — one final copy
    }

    // Method 2: char array — same efficiency, more explicit
    public static String replaceCharArray(String s, int index, char newChar) {
        char[] chars = s.toCharArray();   // O(n) — copy to array
        chars[index] = newChar;           // O(1) — direct write
        return new String(chars);         // O(n) — copy back to String
    }

    // Method 3: substring concatenation — creates multiple objects, avoid
    public static String replaceCharSub(String s, int index, char newChar) {
        return s.substring(0, index) + newChar + s.substring(index + 1);
        // Creates 3 new String objects — O(n) but with higher constant
    }

    public static void main(String[] args) {
        String s = "Hello, World!";

        System.out.println("Original:        " + s);
        System.out.println("Change [0] to 'h': " + replaceCharSB(s, 0, 'h'));
        System.out.println("Change [7] to 'w': " + replaceCharArray(s, 7, 'w'));
        System.out.println("Original still:  " + s);  // Unchanged
    }
}

Output:
Original:        Hello, World!
Change [0] to 'h': hello, World!
Change [7] to 'w': Hello, world!
Original still:  Hello, World!

StringBuilder API Deep Dive (Java)

StringBuilder is the most important mutable string class in Java interviews. Know every method.

Java

public class StringBuilderAPI {

    public static void main(String[] args) {
        // Create with initial content or initial capacity
        StringBuilder sb1 = new StringBuilder("Hello");       // Content
        StringBuilder sb2 = new StringBuilder(100);           // Capacity only, size=0
        StringBuilder sb3 = new StringBuilder();              // Default capacity=16

        StringBuilder sb = new StringBuilder("Hello, World!");

        // --- Reading ---
        System.out.println("length():    " + sb.length());       // 13
        System.out.println("charAt(7):   " + sb.charAt(7));      // 'W'
        System.out.println("toString():  " + sb.toString());     // "Hello, World!"
        System.out.println("substring(0,5): " + sb.substring(0, 5)); // "Hello"
        System.out.println("indexOf('W'): " + sb.indexOf("W"));  // 7

        // --- Appending ---
        sb.append('!');                    // append char
        sb.append(" How are you?");        // append String
        sb.append(42);                     // append int — converts to "42"
        sb.append(3.14);                   // append double
        System.out.println("After append: " + sb);

        // --- Inserting ---
        sb.insert(0, ">>> ");              // Insert at beginning
        sb.insert(8, "[INSERTED]");        // Insert at index 8
        System.out.println("After insert: " + sb);

        // --- Deleting ---
        sb.delete(0, 4);                  // Delete range [0, 4)
        sb.deleteCharAt(0);               // Delete single character
        System.out.println("After delete: " + sb);

        // --- Replacing ---
        sb.replace(0, 5, "Howdy");        // Replace range with new content
        System.out.println("After replace: " + sb);

        // --- Modifying ---
        sb.setCharAt(0, 'h');             // Change one character
        sb.reverse();                      // Reverse all characters in place
        System.out.println("Reversed: " + sb);

        // --- Capacity management ---
        StringBuilder sized = new StringBuilder(1000); // Pre-size for n chars
        System.out.println("Capacity: " + sized.capacity()); // 1000
        // Pre-sizing avoids internal resizes when you know the approximate size
    }
}

Output (Java):
length():    13
charAt(7):   W
After append: Hello, World!! How are you?42 3.14
Reversed: (reversed content)

StringBuffer vs StringBuilder (Java)

Both are mutable string buffers. The only difference is thread safety.

Feature	`StringBuilder`	`StringBuffer`
Thread safety	Not thread-safe	Thread-safe (synchronized)
Performance	Faster	Slower (synchronization overhead)
When to use	Single-threaded code — all interviews	Multi-threaded shared string building
Available since	Java 5	Java 1.0

Rule for interviews: Always use StringBuilder. Interviewers expect it. StringBuffer exists for historical reasons and concurrent scenarios that never appear in algorithm interviews.

StringBuilder for interviews:
  StringBuilder sb = new StringBuilder();
  sb.append("...");
  sb.reverse();
  sb.setCharAt(i, c);
  return sb.toString();

StringBuffer only when:
  Multiple threads share the same buffer AND write to it concurrently
  (Almost never in interview problems)

When to Convert: The Decision Rules

This is the practical guide for making the right choice in every situation.

Keep using String when:
  - You are reading only (no modification needed)
  - You call 1-3 methods that return new strings (s.trim().toLowerCase())
  - The string is used as a hash map key
  - You are comparing strings for equality
  - The string is a function parameter or return value

Switch to StringBuilder (Java) or list (Python/JS) when:
  - You build a string character by character in a loop
  - You need to modify characters at specific indices
  - You do 4+ operations that would each create a new string
  - You need to reverse or rearrange characters efficiently
  - Performance matters and the string is large (n > 1000 characters)

Use char[] (Java) when:
  - You need raw performance without StringBuilder overhead
  - You are implementing sorting or reversal in-place
  - Memory allocation must be minimized (competitive programming)

Convert mutable → immutable when:
  - You need to return the result as a String
  - You need to use String methods (split, contains, indexOf)
  - You need to use the result as a hash map key
  - You are done building and need the final value

Common Interview Patterns Using StringBuilder

These are the most frequent patterns where StringBuilder appears in interview solutions.

Java

import java.util.Stack;

public class StringBuilderPatterns {

    // Pattern 1: Reverse a string
    public static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
        // Or manually: append backward, or use char[] swap
    }

    // Pattern 2: Remove characters matching a condition
    public static String removeVowels(String s) {
        StringBuilder sb = new StringBuilder();
        String vowels = "aeiouAEIOU";

        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) == -1) {
                sb.append(c);    // Only append non-vowels
            }
        }

        return sb.toString();
    }

    // Pattern 3: Build result from processed characters
    public static String encodeRunLength(String s) {
        if (s.isEmpty()) return s;

        StringBuilder sb = new StringBuilder();
        int count = 1;

        for (int i = 1; i <= s.length(); i++) {
            if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                sb.append(s.charAt(i - 1));
                if (count > 1) sb.append(count);
                count = 1;
            }
        }

        return sb.toString();
    }

    // Pattern 4: Decode using a stack
    public static String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();

        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i]);
            if (i > 0) sb.append(" ");
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("reverse:         " + reverse("hello"));
        System.out.println("removeVowels:    " + removeVowels("Hello World"));
        System.out.println("runLength 'aabbccc': " + encodeRunLength("aabbccc"));
        System.out.println("reverseWords:    " + reverseWords("the quick brown fox"));
    }
}

Output:
reverse:         olleh
removeVowels:    Hll Wrld
runLength aabbccc: ab2c3
reverseWords:    fox brown quick the

Interview Questions

Q: In Java, what is the difference between String, StringBuilder, and StringBuffer?

String is immutable — every modification creates a new object. StringBuilder is a mutable character buffer — modifications happen in place, and it uses a doubling strategy like a dynamic array. StringBuilder is not thread-safe. StringBuffer is identical to StringBuilder but synchronized — every method is locked, making it safe for concurrent access at the cost of performance. In interview problems, always use StringBuilder. StringBuffer is a legacy class for multi-threaded use cases that rarely appear in algorithm interviews.

Q: Why does s += "x" in a loop cause O(n²) performance in Java but not in C++?

In Java, String is immutable. Each += creates a new String object containing all previous characters plus the new one. For n iterations, total copies are 0 + 1 + 2 + ... + n-1 = O(n²). In C++, std::string is mutable. += appends to the same internal buffer using a doubling strategy (like vector::push_back). Occasional resizes copy all elements, but across n appends the total copy work is O(n) — same as dynamic array. Python lists used with join() are O(n) for the same reason.

Q: How do you reverse a string in Java without using StringBuilder.reverse()?

Convert to a char[] using toCharArray(), use two-pointer swapping (left and right converge inward, swapping characters), then construct a new String from the modified array. This is O(n) time and O(n) space. Alternatively, build a StringBuilder, append characters by iterating backward, and call toString(). Both approaches are O(n).

Q: When should you choose char[] over StringBuilder in Java?

char[] is slightly faster than StringBuilder because it avoids the StringBuilder's method call overhead and capacity checks. Use char[] when you know the exact final size upfront (no dynamic growth needed), when you are implementing a sorting or in-place manipulation algorithm, or in competitive programming where constant factors matter. For general-purpose string building in interviews, StringBuilder is the clearer choice.

FAQs

Does Python's += on strings create a new object every time?

Semantically yes — s += "x" is equivalent to s = s + "x", creating a new string. However, CPython has an optimization: when a string variable is the only reference to its object, += may extend the existing buffer in place rather than allocating a new one. This makes simple repeated += faster in practice than the worst case suggests. But this optimization is implementation-specific and not guaranteed. For production code and interviews, use the list + join pattern for loop-based string building to guarantee O(n) behavior.

What is the capacity of a StringBuilder when created with new StringBuilder()?

The default capacity in Java is 16 characters. The buffer doubles when capacity is exceeded — the same strategy as ArrayList. Creating with new StringBuilder(n) pre-allocates capacity for n characters, avoiding all resizes if you add at most n characters. Pre-sizing is worth doing in interviews when you know the approximate output length, as it avoids the O(n) resize work entirely.

Can you use a String as a HashMap key after converting it from a StringBuilder?

Yes. Once you call sb.toString(), you get an immutable String object suitable as a HashMap key. Its hash code is computed and cached on first use. You cannot use a StringBuilder directly as a HashMap key — it is mutable, so its hash could change after insertion, making it unfindable.

Is there a performance difference between sb.append('a') and sb.append("a") in Java?

Yes — append(char) is slightly faster than append(String) because it appends one character directly. append(String) requires checking the string length and possibly entering the multi-character copy path. For single characters in tight loops, prefer append((char)('a' + i)) over append(String.valueOf((char)('a' + i))).

Quick Quiz

Question 1: In Java, what is the output of: String s = "hello"; s.toUpperCase(); System.out.println(s);

›A) "HELLO"
›B) "hello" — toUpperCase() returns a new String but s is not reassigned
›C) Compilation error
›D) "Hello"

Answer: B) "hello". toUpperCase() returns a new immutable String object. The original s is never reassigned, so it still holds "hello". To update s, you must write s = s.toUpperCase().

Question 2: You need to build a string by appending 1,000,000 characters in a loop in Java. Which is correct?

›A) String result = ""; for (...) result += c; — O(n²), avoid
›B) StringBuilder sb = new StringBuilder(); for (...) sb.append(c); return sb.toString(); — O(n), correct
›C) Both have the same performance
›D) String.format() inside the loop — O(1) per call

Answer: B) StringBuilder. String += in a loop is O(n²). StringBuilder.append() is amortized O(1) per call, giving O(n) total. String.format() creates a new String object on each call — same O(n²) problem as +=.

Question 3: In Python, what is the efficient way to build a string from a list of n words?

›A) result = ""; for word in words: result += word + " "
›B) result = " ".join(words) — O(total characters), one allocation
›C) result = str(words) — converts list to string representation
›D) result = words[0]; for w in words[1:]: result = result + " " + w

Answer: B) " ".join(words). join() computes the total output size first, makes one allocation, and copies all characters once — O(total characters). Both A and D use repeated +=, which creates a new string at each step — O(n²).

Question 4: In C++, does s += "x" inside a loop cause the same O(n²) problem as Java?

›A) Yes — std::string is immutable like Java's String
›B) No — std::string is mutable, += uses amortized O(1) append
›C) It depends on the string length
›D) Yes — C++ strings create new objects on every modification

Answer: B) No. C++ std::string is mutable. += appends to the same internal buffer using a capacity-doubling strategy. Each push_back equivalent is amortized O(1). Total for n appends is O(n). C++ avoids the immutability trap that Java and Python face.

Summary

Mutable and immutable strings serve different purposes. Immutable strings are safe to share, hash, and compare. Mutable buffers are efficient for building and modifying.

The key ideas to carry forward:

›In Java, Python, and JavaScript, every string "modification" creates a new string — O(n) per operation
›Building a string with + in a loop is O(n²) in Java, Python, and JavaScript — a critical interview anti-pattern
›Use StringBuilder in Java for loop-based string building — O(n) total
›Use list + "".join() in Python for the same purpose
›Use array + .join('') in JavaScript
›C++ std::string is mutable — += is amortized O(1), no special buffer needed
›StringBuilder and StringBuffer are identical except thread safety — use StringBuilder in interviews
›Modifying a character at index i requires converting to a mutable structure first (except C++)
›Pre-sizing StringBuilder with new StringBuilder(n) avoids all resize copies when you know the output length

In the next topic, you will explore Time and Space Complexity of Strings — the complete complexity reference for every string operation and algorithm.

←

PreviousString Operations

NextTime & Space Complexity

→