String Manipulation

String questions combine scanning with representation and output-construction costs. Establish what “character,” equality and matching mean before selecting an array-based technique.

1. Choose the Unit of Text

An ASCII-only contract permits byte indexing and range checks such as 'a' <= c <= 'z'. Arbitrary Unicode requires a deliberate choice: bytes, code points, or user-perceived characters can have different lengths.

Python string iteration works in Unicode code points; Go string indexing yields bytes, while range decodes runes and reports byte offsets. JavaScript indices address UTF-16 code units. Even a code point is not always a whole displayed character: combining marks can belong to the preceding letter. Do not silently apply an ASCII implementation to unrestricted text.

If the task ignores case, spaces or punctuation, define the normalization once and apply it consistently to comparisons and lookups. If original offsets must be returned, keep their mapping when normalization changes length. The character-utility exercise uses explicit ASCII rules.

2. Scan with Explicit Boundaries

For tokenization, keep start at the first character of the current token and advance a scan index. A delimiter closes [start,scan); after the scan, handle the final token. Consecutive delimiters, leading/trailing delimiters and empty input determine whether empty tokens must be preserved. String Split states that contract.

For a naive substring search, test candidate starts only through n-m, where text length is n and pattern length m. Compare within the candidate until a mismatch or all m characters match. Worst-case time is $O((n-m+1)m)$ when m <= n, with $O(1)$ auxiliary space if indices are used. Define the empty-pattern answer; a longer pattern cannot match. A library search may use a better algorithm, so do not infer its runtime from the naive implementation.

Repeated long-prefix matches can motivate KMP: after a mismatch, its prefix-function table identifies the longest matched suffix that is also a pattern prefix, avoiding rescanning the text. Preprocessing plus search is $O(n+m)$ time and $O(m)$ space. Learn it when linear worst-case matching is explicitly required; ordinary token and pointer questions rarely need it.

3. Build the Output Once

Repeatedly appending to immutable strings can copy growing prefixes, with quadratic total work. Collect fragments and join once, or use a builder. If parts contain L characters in total and there are k parts, a separator of length d gives output length L + max(0,k-1)*d.

def join_words(words):
    return ' '.join(words)

Count the output itself: producing L characters requires $O(L)$ work and output space. Nested loops are not automatically quadratic if their total emitted text is only linear; conversely, a single loop can be quadratic if each iteration copies the accumulated string. Python slicing also creates new string data, so use indices when repeatedly processing suffixes.

4. Key Takeaways

• State ASCII versus Unicode and the indexing unit; Go byte offsets and rune counts are not interchangeable.
• For splitting, decide whether empty fields survive and handle the final token explicitly.
• Separate matching cost from output cost; include slicing, normalization and copying in the analysis.
• Build fragments once and join once instead of repeatedly rebuilding a growing immutable result.

Continue to Two Pointers for palindrome/filter scans, Sliding Windows for substring constraints, Sets & Maps for frequency or anagram keys, and Dynamic Programming for subsequences and edit-style states.