Why is building a string in a loop slow in JavaScript?

JavaScript strings are immutable, so s += c may create a whole new string each time, making the loop O(n squared) in the worst case. Push the characters into an array and call join at the end, which is O(n).

How do I count character frequencies efficiently?

For a known small alphabet such as lowercase English letters, use a fixed array of size 26 indexed by c minus 'a'. It is faster than a hash map and makes comparing two counts trivial. Use a hash map only when the character set is large or unknown, such as full Unicode.

Is comparing sorted strings a good way to check for anagrams?

It works and it is only two lines, but it costs O(n log n). Counting characters is O(n) and is the answer interviewers are looking for. Mention both, then implement the counting one.

Strings — ASAPUtils

1. The physical picture

A string is an array of characters. Everything from arrays applies — indexing is O(1), searching is O(n), and slicing copies.

The one difference that actually bites:

C++ std::string is mutable. s[i] = 'x' works; s += c is amortised O(1), same as push_back.
JavaScript strings are immutable. s[i] = 'x' silently does nothing. s += c in a loop can be O(n²) because each concatenation may allocate a fresh string.

The rule: in JavaScript, never build a string with += inside a loop. Push into an array and join('') at the end.

2. The invariant

Characters occupy positions 0 .. length-1 in order, and (in JS) the value never changes once created — every “modification” produces a new string.

3. Operations and complexity

Operation	Cost
`s[i]`	O(1)
Length	O(1)
Concatenate	O(n + m)
Substring / slice	O(k) for length k
Compare two strings	O(min(n, m))
Sort the characters	O(n log n)
Count characters	O(n)

4. C++ and JavaScript

string s = "hello";
s += 'x';                        // amortised O(1) — mutable
s[0] = 'H';                      // fine
int idx = s[i] - 'a';            // 0..25 for lowercase
string t = s.substr(2, 3);
sort(s.begin(), s.end());        // sorts in place
vector<int> freq(26, 0);
for (char c : s) freq[c - 'a']++;

let s = 'hello';
s[0] = 'H';                      // silently does nothing — immutable
const idx = s.charCodeAt(i) - 97;
const t = s.slice(2, 5);
const sorted = [...s].sort().join('');
const freq = new Array(26).fill(0);
for (const c of s) freq[c.charCodeAt(0) - 97]++;

const parts = [];                // build this way, not with +=
for (const c of s) parts.push(c);
const built = parts.join('');

5. How you travel it

Character walk — the default; usually paired with a frequency structure.
Two pointers from the ends — palindromes. Skip non-alphanumerics, compare lowercased.
Sliding window — “longest substring such that…”, which is all of week 2.
Canonical key — map each string to a form that’s identical for the whole group (sorted characters, or a count signature). That’s the entire idea behind Group Anagrams.

6. It’s the answer when…

The input is text and the question is about composition (anagram, permutation, frequency), order (palindrome, subsequence), or grouping (anagrams into buckets).

7. The three classic mistakes

Building with += in a JS loop. Silent O(n²).
Assuming lowercase ASCII. Check the constraints. Uppercase, digits, spaces and Unicode all break a - 'a' index — and a 26-slot array will crash or corrupt memory in C++.
Sorting when counting would do. O(n log n) where O(n) was available. Fine as a first answer, not as the final one.

8. What to drill

Valid Anagram (count, don’t sort), Valid Palindrome (two pointers with filtering), Group Anagrams (canonical key), and Encode/Decode Strings (why a delimiter alone can’t work, and why a length prefix can).

Strings