String Time & Space Complexity

The Complete String Operation Complexity Table

Every string operation has a cost. This is the single reference that covers all of them. The sections below explain why each cost exists.

Why Access Is O(1) but Length Is Also O(1)

Both feel obvious, but their O(1) comes from different places.

Character access is O(1) for the same reason array access is — the address formula:

address of s[i] = base_address + (i × bytes_per_char)

String length is O(1) because every string object stores its length as a field. The length is computed once when the string is created and cached forever. When you call s.length() in Java or len(s) in Python, it reads a stored integer — not a traversal. This is why it is safe to call s.length() inside a loop condition without performance cost.

Java String object (simplified):
  - char[] value    ← the character data
  - int  count      ← the length (O(1) to read)
  - int  hash       ← cached hash code

len(s) in Python:
  - CPython ob_size field on the list object ← O(1) to read

Why String Comparison Is O(min(n, m))

Comparing two strings means checking characters one by one from left to right until a difference is found or one string ends.

Compare "apple" and "application":

  a == a → continue
  p == p → continue
  p == p → continue
  l == l → continue
  e vs i → 'e' (101) < 'i' (105) → "apple" comes before "application"

Steps: 5 (stopped at first difference)
Worst case: O(min(len1, len2)) — when strings share a long common prefix
Best case:  O(1) — when first characters differ

This matters when sorting strings. Sorting n strings of average length k costs O(k × n log n) — not just O(n log n). Each comparison during the sort is O(k), not O(1).

The True Cost of Substring Operations

Every substring / slice operation copies characters into a new memory allocation. It is never free.

Extracting "World" from "Hello, World!" (5 characters):
  s.substring(7, 12) in Java  → allocate 5 chars, copy 5 chars → O(5) = O(k)
  s[7:12] in Python           → allocate 5 chars, copy 5 chars → O(5) = O(k)
  s.slice(7, 12) in JavaScript → allocate 5 chars, copy 5 chars → O(5) = O(k)
  s.substr(7, 5) in C++       → allocate 5 chars, copy 5 chars → O(5) = O(k)

Cost: O(k) time and O(k) space where k = substring length

The danger: creating substrings inside a double loop.

for i in range(n):
    for j in range(i, n):
        sub = s[i:j+1]    ← O(j-i+1) per call, not O(1)

Total substring work:
  Average length: n/2
  Number of substrings: n(n+1)/2
  Total characters copied: O(n) × O(n/2) = O(n³)

The loop LOOKS O(n²) but IS O(n³) due to substring creation.
Working with index pairs (i, j) instead of actual substrings avoids this.

Frequency Array vs Frequency Hash Map

Both track character frequencies, but with very different space behavior.

Frequency array (for lowercase letters only):
  int[] freq = new int[26]
  freq[c - 'a']++

  Time:  O(n) to build — one pass
  Space: O(1) — exactly 26 integers, constant regardless of string length

Frequency hash map (for any character set):
  HashMap<Character, Integer> freq = new HashMap<>()
  freq.put(c, freq.getOrDefault(c, 0) + 1)

  Time:  O(n) to build — one pass
  Space: O(k) where k = number of distinct characters
         Worst case: O(n) if all n characters are distinct
         For lowercase only: O(26) = O(1) — bounded by alphabet size

Always prefer a int[26] frequency array over a hash map when the character set is bounded and known. It is faster (no hashing overhead), uses less memory, and simplifies comparison (compare two arrays of length 26 in O(26) = O(1)).

Output:
Array method — 'anagram' vs 'nagaram': true
Map method   — 'rat' vs 'car':         false

Algorithm Complexity for Common String Problems

Reading Constraints to Predict Required Complexity

String constraints work differently from integer array constraints because both string length and character set matter.

n = length of the string or number of strings

n ≤ 20:
  Exponential solutions acceptable (O(2^n) or O(n!))
  Backtracking over all permutations/subsets

n ≤ 1,000:
  O(n²) acceptable — nested loops, naive pattern search
  O(n² × m) may time out

n ≤ 100,000 (10^5):
  O(n²) is too slow — 10^10 operations
  Need O(n log n) or O(n)
  Sliding window, frequency arrays, KMP

n ≤ 1,000,000 (10^6):
  Must be O(n) or O(n log n)
  Single pass algorithms, rolling hash

Character set signal:
  "lowercase letters only" → int[26] freq array → O(1) space
  "ASCII characters"       → int[128] freq array → O(1) space
  "Unicode / any char"     → hash map → O(n) space

Space Complexity of String Algorithms

String space complexity has three common patterns:

O(1) auxiliary space — algorithms that use only a constant number of variables, no new strings. Two-pointer palindrome check, character counting with a fixed-size array.

O(n) auxiliary space — algorithms that create a new string, a hash map, or an auxiliary array proportional to input size. Most string operations return new strings.

O(m) auxiliary space — algorithms that store the pattern or a preprocessing structure. KMP stores the failure function of length m.

Pattern → Space complexity:

  Two-pointer palindrome:      O(1)  — two index variables
  Frequency array (26 chars):  O(1)  — fixed 26-element array
  Frequency hash map:          O(k)  — k = distinct chars, worst O(n)
  Reverse a string:            O(n)  — new string allocation
  Split result:                O(n)  — array of substrings
  StringBuilder build:         O(n)  — internal char buffer
  Sliding window with hash set:O(k)  — k = distinct chars in window
  KMP failure function:        O(m)  — m = pattern length
  Suffix array:                O(n)  — array of n indices

Output:
isPalindrome 'racecar': true
firstUnique 'leetcode':  l
reverse 'hello':         olleh

Brute Force vs Optimized: Complexity Pairs

The Sorting Complexity Trap in String Problems

Sorting a string (to check anagrams, find lexicographic order, etc.) costs O(n log n) — not O(1) or O(n). This is frequently underestimated.

Sorting "anagram" to get "aaagmnr":
  Convert to char array: O(n)
  Sort the array:        O(n log n)
  Convert back:          O(n)
  Total: O(n log n)

For n strings each of length k:
  Sort each string:    O(n × k log k)
  Group by sorted key: O(n × k) for hash map insertions
  Total: O(n × k log k)

This is often the bottleneck in groupAnagrams — not the grouping,
but the per-string sort. The frequency array alternative avoids it:
  Encode each string as its frequency array: O(k)
  No sorting needed
  Total: O(n × k) — saves the log k factor

Hidden Complexity: What Looks O(1) But Is Not

Several operations appear cheap but are actually O(n) or worse. These cause subtle bugs in complexity analysis.

Operation                        Looks Like    Actually Is
s.equals(t) in Java              O(1)?         O(min(n,m)) char-by-char compare
s.hashCode() first call          O(1)?         O(n) — computes and caches hash
"hello" + "world"                O(1)?         O(n+m) — allocates and copies
s.substring(i, j) in Java       O(1)?         O(j-i) — allocates and copies
s.toCharArray() in Java          O(1)?         O(n) — copies all chars to new array
[...s] spread in JavaScript      O(1)?         O(n) — iterates and copies all chars
s.split(",") in Java             O(1)?         O(n) — scans entire string

Truly O(1):
  s.length()        → reads stored field
  s.charAt(i)       → address computation
  s.isEmpty()       → checks stored length == 0

Practical Complexity Checklist for String Problems

Step 1: Identify what varies with n.
  n = string length? n = number of strings? k = pattern length?
  Separate variables — O(n × m) has TWO inputs, not one.

Step 2: Count character-level operations.
  Each character visited once: O(n)
  Each pair of characters: O(n²)
  Substring creation inside a loop: add O(k) per call
  Sorting: O(n log n)

Step 3: Account for space.
  New string returned: O(n)
  Fixed alphabet array (26): O(1)
  Hash map with n distinct chars: O(n)
  StringBuilder buffer: O(n)

Step 4: Watch for hidden O(n) operations inside what looks like O(1).
  Any string method that returns a new string: O(length of result)
  .toCharArray(): O(n)
  .equals(): O(n) worst case
  .hashCode() (first call): O(n)

Step 5: Check if the character set bound reduces space complexity.
  "lowercase letters" → any freq structure has at most 26 entries → O(1)
  "ASCII" → at most 128 entries → O(1)
  "Unicode" → unbounded → O(n)

Interview Questions

Q: What is the time complexity of checking if two strings are anagrams, and what is the best approach?

The optimal approach is O(n) time and O(1) space (for lowercase letters). Build a frequency array of size 26. Increment for each character in the first string, decrement for each in the second. If any entry is nonzero, they are not anagrams. Sorting both strings and comparing costs O(n log n) and is less efficient. Using a hash map costs O(n) time but O(n) space, which is worse than the frequency array for a fixed alphabet.

Q: Why does creating substrings inside a double loop make the algorithm O(n³) instead of O(n²)?

Each substring of length k costs O(k) to allocate and copy. A double loop over all (i, j) pairs generates O(n²) pairs with average length O(n/2). Total substring work: O(n²) × O(n/2) = O(n³). Working with index pairs (i, j) without creating actual substrings avoids the extra O(n) factor per pair.

Q: What is the time complexity of sorting all n strings in a list, where each string has average length k?

O(n × k log k) for sorting each individual string (converting to char array, sorting, converting back). The hash map grouping after sorting adds O(n × k) for storing the sorted keys. Total: O(n × k log k). The frequency array optimization removes the inner sort, reducing to O(n × k).

Q: What is the difference in space complexity between using a frequency array and a frequency hash map?

For a bounded alphabet (lowercase letters — 26, ASCII — 128), a frequency array uses O(1) space — the array size is constant regardless of input size. A hash map uses O(k) space where k is the number of distinct characters. For lowercase letters, k ≤ 26, so the hash map is also O(1) in practice — but with higher constant factors. For Unicode strings with unbounded character sets, the hash map uses O(n) space in the worst case.

FAQs

Is s.length() in Java O(1) or O(n)?

O(1). The length field of a String object is set when the string is created and never changes (strings are immutable). Reading it is a single field access — no traversal. Similarly, len(s) in Python reads a stored size field in the list object — O(1). This is safe to call inside loop conditions without performance concern.

Does calling .equals() on a string always cost O(n)?

No. It is O(1) in the best case and O(n) in the worst case. Java first checks if the lengths differ — if they do, it returns false immediately in O(1). If lengths are equal, it checks characters until a difference is found. If the strings are equal or share a very long common prefix, it approaches O(n). The worst case is O(n) — comparing two identical strings of length n.

If I call s.hashCode() multiple times in Java, is it O(n) each time?

No. Java caches the hash code on the first computation. The first call is O(n) — it visits every character. Subsequent calls return the cached value in O(1). This is why strings are efficient as HashMap keys — the hash is computed once and reused. However, the first lookup for a never-before-hashed string does pay the O(n) cost.

Does Python's in operator for strings cost O(n) or O(1)?

"pattern" in string costs O(n × m) where n is the string length and m is the pattern length — it is a substring search, not a hash lookup. "char" in set_of_chars is O(1) — hash set membership. This is a critical distinction: c in "aeiou" is O(5) = O(1) for the vowel check because the pattern set is tiny, but s2 in s1 for long strings is O(n × m).

Quick Quiz

Question 1: You call s.substring(0, n/2) inside a loop that runs n times. What is the total time complexity?

• ›A) O(n) — substring is O(1)
• ›B) O(n log n) — substring is O(log n)
• ›C) O(n²) — each substring call is O(n/2), done n times
• ›D) O(n³) — two nested operations

Answer: C) O(n²). Each substring(0, n/2) call copies n/2 characters — O(n/2) = O(n). Called n times inside a loop: O(n) × O(n) = O(n²). Never assume substring is free.

Question 2: For checking if two strings are anagrams, a frequency array uses O(?) space while a hash map uses O(?) space (both for lowercase letters only).

• ›A) O(n) and O(n)
• ›B) O(1) and O(n)
• ›C) O(1) and O(1) — both bounded by 26
• ›D) O(26) = O(1) and O(26) = O(1)

Answer: C/D) Both are O(1) for lowercase letters. The frequency array is always exactly 26 integers. The hash map has at most 26 entries for lowercase letters — also bounded by the alphabet size, so O(26) = O(1). The distinction matters for Unicode inputs where the hash map could hold O(n) entries.

Question 3: Sorting n strings each of length k has time complexity:

• ›A) O(n log n)
• ›B) O(n × k)
• ›C) O(n × k log k)
• ›D) O(n × k log n)

Answer: C) O(n × k log k). Each string takes O(k log k) to sort (convert to char array, sort k chars, convert back). Done for n strings: O(n × k log k). The O(log n) factor applies to sorting the n strings by their sorted representations, adding O(n log n × k) for that step — but the dominant bottleneck is usually the per-string sort.

Question 4: The operation "abc" in s in Python where s has length n costs:

• ›A) O(1) — Python string membership is hashed
• ›B) O(n) — linear scan for first character
• ›C) O(3n) = O(n) — scans for a 3-character pattern
• ›D) O(n × 3) = O(n) — naive substring search for m=3 character pattern

Answer: D) O(n × m) = O(3n) = O(n). Python's in operator for strings is a substring search — O(n × m) where m is the length of the left operand. For "abc" in s, m=3, so total is O(3n) = O(n). This is NOT O(1) hash lookup. Set membership like 'a' in {'a', 'e', 'i'} is O(1).

Summary

String complexity analysis requires tracking more variables than array complexity — string length n, pattern length m, character set size k, and number of strings. Every one of these affects the final complexity.

The key costs to carry as permanent intuition:

• ›charAt(i) and length() → O(1) — direct reads, never traversals
• ›String equality check → O(n) worst case, O(1) best case
• ›Substring creation → O(k) time and O(k) space where k = substring length
• ›indexOf(pattern) → O(n × m) — naive scan, not O(n)
• ›Concatenation with + in a loop → O(n²) — the critical anti-pattern
• ›StringBuilder append → O(1) amortized — always use for loop building
• ›Frequency array (26 chars) → O(n) build, O(1) space
• ›Frequency hash map → O(n) build, O(k) or O(n) space
• ›String comparison and sorting → O(k) per comparison, O(k log k) to sort one string
• ›Sorting n strings → O(n × k log k) total
• ›Substring in double loop → O(n³) not O(n²)

In the next topic, you will explore Palindrome — the most important string interview concept, with all variations, optimization approaches, and the Manacher's algorithm for O(n) longest palindrome.