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

String Operations

Operations vs Traversal

String traversal covers how to move through a string. String operations cover what you can do with a string using built-in methods — searching for substrings, splitting on delimiters, replacing content, trimming whitespace, and converting between cases.

Knowing the correct method call is only half the skill. Knowing the time complexity of each operation is what prevents hidden O(n²) bugs — and what interviewers test when they ask you to analyze your solution.

Every operation covered here is O(n) or O(n × m) at its worst. None is O(1). Understanding why clarifies when to precompute, cache, or avoid repeated calls.

Operation 1: Search — Finding Characters and Substrings

Finding a Character or Substring

Returns the index of the first occurrence, or -1 if not found.

Java

public class SearchOperations {

    public static void main(String[] args) {
        String s = "the quick brown fox jumps over the lazy dog";

        // indexOf — first occurrence, O(n × m) where m = pattern length
        System.out.println("indexOf 'fox':       " + s.indexOf("fox"));      // 16
        System.out.println("indexOf 'the':       " + s.indexOf("the"));      // 0
        System.out.println("indexOf 'cat':       " + s.indexOf("cat"));      // -1

        // indexOf with fromIndex — search starting at a given position
        System.out.println("indexOf 'the' from 1:" + s.indexOf("the", 1));   // 31

        // lastIndexOf — last occurrence, O(n × m)
        System.out.println("lastIndexOf 'the':   " + s.lastIndexOf("the"));  // 31

        // contains — returns boolean, O(n × m) internally
        System.out.println("contains 'fox':      " + s.contains("fox"));     // true
        System.out.println("contains 'cat':      " + s.contains("cat"));     // false

        // startsWith and endsWith — O(m) where m = prefix/suffix length
        System.out.println("startsWith 'the':    " + s.startsWith("the"));   // true
        System.out.println("endsWith 'dog':      " + s.endsWith("dog"));     // true
    }
}

Output:
indexOf 'fox':       16
indexOf 'the':       0
indexOf 'cat':       -1
indexOf 'the' from 1: 31
lastIndexOf 'the':   31
contains 'fox':      true
startsWith 'the':    true
endsWith 'dog':      true

Search Complexity

Operation              Time Complexity   Notes
indexOf(char)          O(n)              Scan for single character
indexOf(pattern)       O(n × m)          Naive substring search, m = pattern length
lastIndexOf(pattern)   O(n × m)          Scan from right
contains(pattern)      O(n × m)          Calls indexOf internally
startsWith(prefix)     O(m)              Only checks first m characters
endsWith(suffix)       O(m)              Only checks last m characters

Hidden trap: calling indexOf(pattern) inside a loop
  for each of n words, check if pattern is present → O(n × n × m) = O(n²m)
  Use a hash set if you need repeated membership checks

Operation 2: Split — Breaking a String into Parts

Split divides a string into an array of substrings at each occurrence of a delimiter.

Java

import java.util.Arrays;

public class SplitOperation {

    public static void main(String[] args) {
        String csv    = "Alice,Bob,Charlie,David";
        String spaced = "  hello   world   foo  ";
        String path   = "usr/local/bin/java";

        // split(delimiter) — O(n) where n = string length
        String[] names = csv.split(",");
        System.out.println("CSV split:   " + Arrays.toString(names));
        System.out.println("Count:       " + names.length);

        // split("\\s+") — one or more whitespace characters
        String[] words = spaced.trim().split("\\s+");
        System.out.println("Space split: " + Arrays.toString(words));

        // split with limit — stop after limit parts
        String[] parts = csv.split(",", 2);
        System.out.println("Limit 2:     " + Arrays.toString(parts)); // ["Alice", "Bob,Charlie,David"]

        // split on forward slash
        String[] segments = path.split("/");
        System.out.println("Path split:  " + Arrays.toString(segments));

        // Edge case: empty string
        String empty = "";
        String[] emptyParts = empty.split(",");
        System.out.println("Empty split: " + Arrays.toString(emptyParts) + " length=" + emptyParts.length);
    }
}

Output:
CSV split:   [Alice, Bob, Charlie, David]
Count:       4
Space split: [hello, world, foo]
Limit 2:     [Alice, Bob,Charlie,David]
Path split:  [usr, local, bin, java]

Critical Split Differences Across Languages

Behavior              Java              Python          JavaScript
No-arg split          split("\\s+")     split()         split(/\s+/)
                      (must provide)    (auto strips)   (with trim())

Trailing empty strings split(",") on    split(",") on   split(",") on
on "a,b,"             ["a","b",""]      ["a","b",""]    ["a","b",""]
                      ← Java drops!     ← Python keeps  ← JS keeps

Limit parameter       stops AFTER       stops AFTER     DIFFERENT —
on split(",", 2)      limit-1 delims    limit-1 delims  limits RESULT count,
                      remaining joined  remaining joined not delimiter count

Empty string split    [""] length=1     [""] length=1   [""] length=1
""  → split(",")

Operation 3: Join — Building Strings from Parts

Join is the inverse of split — it combines an array of strings into one, with a separator between each element.

Java

import java.util.Arrays;
import java.util.List;

public class JoinOperation {

    public static void main(String[] args) {
        String[] words = {"The", "quick", "brown", "fox"};
        List<String> letters = Arrays.asList("a", "b", "c", "d");

        // String.join(delimiter, array/iterable) — O(total character count)
        String sentence = String.join(" ", words);
        System.out.println("Join with space: " + sentence);

        String csv = String.join(",", letters);
        System.out.println("Join with comma: " + csv);

        String noSep = String.join("", words);
        System.out.println("Join with empty: " + noSep);

        // Join with a multi-character separator
        String pathSep = String.join(" | ", words);
        System.out.println("Join with pipe:  " + pathSep);
    }
}

Output:
Join with space: The quick brown fox
Join with comma: a,b,c,d
Join with empty: Thequickbrownfox
Join with pipe:  The | quick | brown | fox

Operation 4: Replace — Substituting Content

Replace returns a new string with occurrences of a pattern substituted with a replacement. The original string is never modified.

Java

public class ReplaceOperation {

    public static void main(String[] args) {
        String s = "the cat sat on the mat";

        // replace(char, char) — replace all occurrences of a character
        String noT = s.replace('t', 'X');
        System.out.println("replace 't' → 'X': " + noT);

        // replace(String, String) — replace all occurrences of a substring
        String noCat = s.replace("cat", "dog");
        System.out.println("replace 'cat':     " + noCat);

        // replaceFirst — only the first occurrence
        String first = s.replaceFirst("the", "a");
        System.out.println("replaceFirst 'the':" + first);

        // replaceAll with regex — replace all matches of a pattern
        String digits = "a1b2c3d4".replaceAll("[0-9]", "#");
        System.out.println("remove digits:     " + digits);

        String noSpaces = "hello   world".replaceAll("\\s+", " ");
        System.out.println("collapse spaces:   " + noSpaces);

        // Original is unchanged
        System.out.println("Original:          " + s);
    }
}

Output:
replace 't' → 'X': Xhe caX saX on Xhe maX
replace 'cat':     the dog sat on the mat
replaceFirst 'the':a cat sat on the mat
remove digits:     a#b#c#d#
Original:          the cat sat on the mat

Replace Complexity and the JavaScript `replace` Trap

replace(char, char)      → O(n) — scan and replace each char
replace(str, str)        → O(n × m) per replacement, r replacements → O(n × m × r)
replaceAll with regex    → depends on regex complexity

JavaScript trap:
  "aaa".replace("a", "b")       → "baa"  ← only FIRST occurrence!
  "aaa".replaceAll("a", "b")    → "bbb"  ← all occurrences (ES2021)
  "aaa".replace(/a/g, "b")      → "bbb"  ← regex with g flag (older approach)

Java: replace(String, String) replaces ALL occurrences — no trap
Python: replace(old, new) replaces ALL occurrences — no trap

Operation 5: Trim — Removing Whitespace

Trim removes leading and trailing whitespace. It does not touch whitespace in the middle of a string.

Java

public class TrimOperation {

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

        // trim() — removes leading and trailing whitespace, O(n)
        System.out.println("Original: '" + s + "'");
        System.out.println("trim():   '" + s.trim() + "'");
        System.out.println("Length before: " + s.length());
        System.out.println("Length after:  " + s.trim().length());

        // Java 11+: strip() handles Unicode whitespace; trim() only handles ASCII
        System.out.println("strip():  '" + s.strip() + "'");
        System.out.println("stripLeading(): '" + s.stripLeading() + "'");
        System.out.println("stripTrailing(): '" + s.stripTrailing() + "'");

        // trim does NOT remove internal whitespace
        String internal = "hello   world";
        System.out.println("Internal whitespace: '" + internal.trim() + "'");
        // → 'hello   world' — middle spaces unchanged
    }
}

Output:
Original: '   Hello, World!   '
trim():   'Hello, World!'
Length before: 20
Length after:  13
Internal whitespace: 'hello   world'

Operation 6: Case Conversion

Convert all characters to uppercase or lowercase. O(n) — every character is visited.

Java

public class CaseConversion {

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

        System.out.println("Original:   " + mixed);
        System.out.println("toUpper:    " + mixed.toUpperCase());
        System.out.println("toLower:    " + mixed.toLowerCase());

        // Case-insensitive comparison — always lowercase both, then compare
        String a = "Hello";
        String b = "HELLO";
        System.out.println("Equal (case-insensitive): "
            + a.toLowerCase().equals(b.toLowerCase()));  // true
        // Equivalent: a.equalsIgnoreCase(b)

        // Check if a character is uppercase/lowercase
        for (char c : mixed.toCharArray()) {
            if (Character.isLetter(c)) {
                System.out.print(Character.isUpperCase(c) ? "U" : "l");
            } else {
                System.out.print("-");
            }
        }
        System.out.println();
    }
}

Output:
Original:   Hello, World! 123
toUpper:    HELLO, WORLD! 123
toLower:    hello, world! 123
Equal (case-insensitive): true

Operation 7: Checking String Properties

Quick boolean checks that answer common interview questions without building new strings.

Java

public class StringChecks {

    public static void main(String[] args) {
        String empty     = "";
        String blank     = "   ";
        String alpha     = "hello";
        String alphaNum  = "hello123";
        String numeric   = "12345";
        String mixed     = "Hello World";

        // Empty and blank checks — O(1) and O(n) respectively
        System.out.println("isEmpty (empty):  " + empty.isEmpty());   // true
        System.out.println("isEmpty (blank):  " + blank.isEmpty());   // false
        System.out.println("isBlank (blank):  " + blank.isBlank());   // true (Java 11+)

        // Character-level checks using Character class — O(n) each
        System.out.println("All letters (alpha): "
            + alpha.chars().allMatch(Character::isLetter));            // true
        System.out.println("All alNum  (alphaNum): "
            + alphaNum.chars().allMatch(Character::isLetterOrDigit));  // true
        System.out.println("All digits (numeric): "
            + numeric.chars().allMatch(Character::isDigit));           // true

        // Simple manual check (clearer in interviews)
        boolean allDigits = true;
        for (char c : numeric.toCharArray()) {
            if (!Character.isDigit(c)) { allDigits = false; break; }
        }
        System.out.println("Manual all digits:   " + allDigits);      // true
    }
}

Output:
isEmpty (empty):  true
isEmpty (blank):  false
isBlank (blank):  true
All letters:      true
All digits:       true

Operation 8: Converting Between String and Number

A frequent requirement in interview problems — converting numeric strings to integers for arithmetic, or integers to strings for output.

Java

public class StringNumberConversion {

    public static void main(String[] args) {
        // String to integer — O(n)
        String numStr = "12345";
        int num = Integer.parseInt(numStr);
        System.out.println("parseInt: " + num + " + 1 = " + (num + 1));

        // Integer to string — O(log n) for the number of digits
        int value = 42;
        String str = String.valueOf(value);        // recommended
        String str2 = Integer.toString(value);     // equivalent
        String str3 = "" + value;                  // works but creates extra object
        System.out.println("valueOf:  " + str + str2);

        // Handle invalid input
        try {
            int bad = Integer.parseInt("not_a_number");
        } catch (NumberFormatException e) {
            System.out.println("Invalid input: NumberFormatException caught");
        }

        // String to double
        double d = Double.parseDouble("3.14");
        System.out.println("parseDouble: " + d);
    }
}

Output:
parseInt: 12345 + 1 = 12346
valueOf:  4242
Invalid input: NumberFormatException caught
parseDouble: 3.14

Operation Complexity Summary

Operation	Time	Notes
`indexOf(char)`	O(n)	Single char scan
`indexOf(pattern)`	O(n × m)	Naive search, m = pattern length
`contains(pattern)`	O(n × m)	Calls indexOf internally
`startsWith(prefix)`	O(m)	Only checks first m chars
`endsWith(suffix)`	O(m)	Only checks last m chars
`split(delimiter)`	O(n)	One pass through the string
`join(parts)`	O(total chars)	Copies all characters once
`replace(old, new)`	O(n × m × r)	r = number of replacements
`trim()` / `strip()`	O(n)	Scan from both ends
`toUpperCase()` / `toLower()`	O(n)	Visit every character
`substring(l, r)`	O(r - l)	Copies r-l characters
`parseInt()`	O(n)	Processes each digit
`equals()`	O(n) worst case	Compares char by char
`length()`	O(1)	Stored as a field
`charAt(i)`	O(1)	Direct address computation

Common Mistakes Beginners Make

Using replace in JavaScript for all occurrences. "aaa".replace("a", "b") returns "baa" — only the first match is replaced. Use replaceAll("a", "b") or replace(/a/g, "b") for global replacement. Java and Python replace all occurrences by default.

Calling indexOf in a loop without understanding the cost. indexOf(pattern) is O(n × m). Calling it inside a loop of n iterations makes the total O(n² × m). If you need to check many patterns against many strings, use a hash set or precompute.

Splitting on " " (single space) instead of "\\s+". "hello world".split(" ") in Java produces ["hello", "", "world"] — an empty string between the two spaces. Split on the regex "\\s+" to handle any whitespace including multiple consecutive spaces.

Not trimming before splitting. " hello world ".split("\\s+") in Java produces ["", "hello", "world"] — an empty string at the beginning from the leading space. Always trim() first.

Treating trim() as removing all whitespace. trim() only removes leading and trailing whitespace. "hello world".trim() returns "hello world" unchanged. To collapse internal whitespace, use replaceAll("\\s+", " ") after trimming.

Converting number to string with "" + num in Java. "" + num creates an intermediate empty String object, then concatenates — marginally less efficient than String.valueOf(num). In interviews, String.valueOf() signals awareness of this.

Interview Questions

Q: What is the time complexity of String.contains() in Java?

O(n × m) where n is the string length and m is the pattern length. contains() internally calls indexOf(), which uses a naive character-by-character scan of the string for each starting position. For a 1000-character string and a 10-character pattern, the worst case is 10,000 character comparisons.

Q: Why does split("\\s+") require double backslash in Java?

Java string literals interpret \ as an escape character. To pass a literal backslash to the regex engine, you write \\ in the Java string (which becomes a single \ at runtime). The regex engine then sees \s+ and interprets \s as the whitespace character class. Python uses r'\s+' (raw string) to avoid the same issue.

Q: What is the difference between isEmpty() and isBlank() in Java?

isEmpty() returns true only if the string has zero characters — "". isBlank() (Java 11+) returns true if the string contains only whitespace — "", " ", "\t\n". Use isEmpty() for checking no characters, isBlank() for checking no meaningful content.

Q: How do you reverse a string without using a built-in reverse method?

Build the reversed string by iterating backward and appending each character to a StringBuilder (Java), a list then joining (Python), building a result string left-to-right by appending from the right end (all languages), or using two-pointer swap on a char[] (Java) or list (Python). The key insight is that strings are immutable in Java, Python, and JavaScript — you cannot reverse in-place, so you must create a new structure.

FAQs

Does split() in Python handle trailing empty strings like Java?

Python's split() with a delimiter argument keeps trailing empty strings: "a,b,".split(",") returns ['a', 'b', '']. Java's split() silently drops trailing empty strings by default — same input returns ['a', 'b']. To keep them in Java: split(",", -1). This difference trips up developers who switch between languages.

Is String.valueOf(int) faster than Integer.toString(int) in Java?

They produce identical output and have the same performance — String.valueOf(int) calls Integer.toString(int) internally. The choice is style. String.valueOf() is slightly more general (handles null for object arguments) while Integer.toString() is more explicit about what it is converting.

In Python, does str.replace() modify the original string?

No. Python strings are immutable. s.replace(old, new) returns a new string with replacements applied. The original s is unchanged. You must reassign: s = s.replace(old, new) to "update" the variable. This is different from C++ where std::string::replace() modifies the string in place.

What is the fastest way to check if a string contains only digits?

In Python: s.isdigit() — O(n), clean, handles edge cases. In Java: s.matches("\\d+") — compiles the regex each call, can be slow for repeated checks; better to use Integer.parseInt() in a try-catch or a manual loop. In C++: all_of(s.begin(), s.end(), ::isdigit) — O(n), efficient. The manual loop with early exit is optimal in all languages when you need to stop as soon as a non-digit is found.

Quick Quiz

Question 1: "hello world".indexOf("world") returns:

›A) 5
›B) 6
›C) 4
›D) -1

Answer: B) 6. The string "hello world" has 'w' at index 6 (h=0, e=1, l=2, l=3, o=4, space=5, w=6). indexOf returns the starting index of the first character of the found substring.

Question 2: What does "a,b,,c,".split(",") return in Java?

›A) ["a", "b", "", "c", ""]
›B) ["a", "b", "", "c"]
›C) ["a", "b", "c"]
›D) ["a", "b", " ", "c", " "]

Answer: B) ["a", "b", "", "c"]. Java's split(delimiter) keeps interior empty strings (between b and c) but silently drops trailing empty strings (the empty string after the final comma). To keep trailing empty strings, use split(",", -1).

Question 3: In JavaScript, "aaa".replace("a", "b") returns:

›A) "bbb" — all occurrences replaced
›B) "baa" — only first occurrence replaced
›C) "aba" — every other occurrence replaced
›D) "aab" — only last occurrence replaced

Answer: B) "baa". JavaScript's replace(string, replacement) replaces only the first occurrence. To replace all, use replaceAll("a", "b") or replace(/a/g, "b").

Question 4: What is the time complexity of String.join(" ", arrayOfNWords) where each word has average length k?

›A) O(n)
›B) O(k)
›C) O(n × k)
›D) O(n²)

Answer: C) O(n × k). Join copies every character from every word into a new string, plus n-1 separator characters. Total characters = n × k + (n-1) × 1 = O(n × k). This is the minimum possible cost for join — you cannot produce the result without writing each output character exactly once.

Summary

String operations fall into two categories: those that take O(1) by reading stored metadata (length(), charAt(i)) and those that must scan characters and therefore cost O(n) or more.

The key operations and their complexities:

›charAt(i) and length() → O(1) — direct property reads
›indexOf(pattern), contains() → O(n × m) — naive scan
›startsWith(prefix), endsWith(suffix) → O(m) — check first or last m chars only
›split(delimiter) → O(n) — single pass
›join(parts) → O(total characters) — copy every character once
›replace(old, new) → O(n × m × r) — depends on pattern and replacement count
›trim(), toUpperCase(), toLowerCase() → O(n) — visit every character
›substring(l, r) → O(r - l) — copy r-l characters

Watch for these recurring traps: replace in JavaScript replaces only the first occurrence; split(" ") leaves empty strings for multiple spaces; trim() does not touch internal whitespace; indexOf called inside a loop gives O(n²).

In the next topic, you will explore Mutable vs Immutable Strings — understanding StringBuilder, StringBuffer, why they exist, and exactly when to use each.

←

PreviousString Traversal

NextMutable vs Immutable Strings

→