String Internals, Immutability, and the Patterns That Win Coding Interviews

Every coding interview has strings. Not most. Every single one. Most engineers treat them like plain arrays of characters and then wonder why their solutions time out, use twice the expected memory, or silently mangle emoji.

Understanding strings at the implementation level is the highest-ROI prep for a string coding interview. It takes maybe thirty minutes. The payoff is permanent: you stop guessing which operations are cheap, you recognize the sliding window and two-pointer patterns on sight, and you stop writing O(n²) loops that look innocent until they hit a 100k-character input.

What a String Actually Is

A string is an immutable sequence of characters backed by a contiguous buffer of bytes. Immutability is the most important word in that sentence. It shapes every complexity analysis and every performance decision that follows.

The one-line mental model: a string is a read-only view into a byte buffer, with encoding metadata telling you how to interpret those bytes as characters.

Reach for strings when you are representing text, parsing structured input, or matching patterns. Reach for a StringBuilder or equivalent when you are building text incrementally.

How a String Lives in Memory

Before the complexity table, you need a picture of what actually sits in RAM. The answer differs significantly by language, and the differences are not academic.

Each language makes different tradeoffs between simplicity, compactness, and safety. C is minimal. Rust is opinionated. Python is sneakily adaptive.

The C Baseline: Null-Terminated Byte Arrays

C is where strings started, and the design is as minimal as possible. A C string is a char array that ends with a zero byte ('\0'). That's it. No length field, no encoding metadata, no capacity.

"hello" in memory (C):

Address:  0x1000  0x1001  0x1002  0x1003  0x1004  0x1005
Value:    'h'     'e'     'l'     'l'     'o'     '\0'
           104     101     108     108     111       0

The consequence: strlen is O(n). Every time you ask how long a string is, C walks the array looking for '\0'. If you forget the null terminator in a fixed-size buffer, you get a buffer overflow. C strings are the source of a significant chunk of all security vulnerabilities ever found in software. Every CVE where memory wandered somewhere it should not have is C saying hello from wherever the null byte ended up.

Python: Four Representations in One Type

Python 3.3+ uses the flexible string representation from PEP 393. Python picks the most compact encoding that can represent every character in the string, and never changes that choice after creation.

There are four internal representations:

Python string memory layout (PEP 393):

┌─────────────────────────────────────────┐
│  PyASCIIObject header (48 bytes)        │
│  ob_refcnt | ob_type | length | hash    │
│  state (kind/compact/ascii flags)       │
│  wstr pointer (deprecated)              │
├─────────────────────────────────────────┤
│  character data (1 byte each for ASCII) │
│  h  e  l  l  o                          │
└─────────────────────────────────────────┘

The whole object is one allocation. The header and the character data are contiguous. For ASCII strings, the UTF-8 representation and the raw bytes are identical, so Python can serve both without extra work.

The sneaky cost: add one emoji to an otherwise-ASCII string, and Python upgrades the entire string to 4-byte UCS-4. A thousand-character string of ASCII plus one smiley face takes 4 KB instead of 1 KB. One emoji. Four times the memory. Your user input field is a liability waiting for someone to paste a flag.

Java: Compact Strings Since Java 9

Before Java 9, every String stored its characters as a char[]. A char in Java is a UTF-16 code unit: always two bytes, even for 'A'. So the string "hello" consumed 10 bytes of character data plus object overhead.

JEP 254 (Compact Strings) shipped with Java 9 and changed the internal layout to a byte[] plus a one-byte coder field.

Java String (Java 9+):

┌───────────────────────────┐
│  Object header            │
├───────────────────────────┤
│  byte[] value             │──→ [h][e][l][l][o]   (Latin-1, 1 byte each)
├───────────────────────────┤
│  byte coder = LATIN1 (0)  │   or UTF16 (1)
├───────────────────────────┤
│  int hash                 │
└───────────────────────────┘

If every character fits in Latin-1 (code point ≤ 255), the coder is 0 and each character takes one byte. If any character needs more, everything upgrades to UTF-16 at two bytes per character. The JVM handles the switching transparently.

That change pays off in practice. Most application strings (variable names, log messages, user input from Latin-alphabet keyboards) are all-Latin-1. Java 9 cut heap usage for those by roughly 50%.

JavaScript: The UTF-16 Trap

The ECMAScript specification defines strings as sequences of 16-bit UTF-16 code units. The V8 engine adds its own optimizations on top: SeqOneByteString for ASCII-only strings (1 byte per char), SeqTwoByteString for anything else (2 bytes per char), plus lazy representations like ConsString for concatenations that have not yet been flattened.

The trap is .length. In JavaScript, .length counts code units, not characters. This is not a gotcha buried in the spec. This is a test case your interviewer has copy-pasted into the console to watch candidates debug.

Slicing at an arbitrary .length boundary can cut a surrogate pair in half. Your "reversed string" becomes gibberish. The fix: [...str] or Array.from(str) iterate over code points instead.

const flag = "🇺🇸";
console.log(flag.length); // 4, not 1. Two surrogate pairs.

const smiley = "😀";
console.log(smiley.length); // 2, not 1. One surrogate pair.

Code points above U+FFFF (emoji, many historic scripts) need two code units each: a high surrogate (U+D800 to U+DBFF) paired with a low surrogate (U+DC00 to U+DFFF). If you split a string at an arbitrary .length boundary, you can slice a surrogate pair in half and get garbage.

This is one of the most common off-by-one categories in string problems. Interviewers love it. Not in a kind way.

Go: A Pointer and a Length

Go strings are a two-word struct: a pointer to byte data and an integer length.

Go string header (16 bytes on 64-bit):

┌──────────────────┐
│  Data *byte      │──→ [h][e][l][l][o]  (UTF-8 encoded bytes)
├──────────────────┤
│  Len  int        │    5
└──────────────────┘

len(s) returns the byte count, not the character count. Iterating with for i, c := range s gives you Unicode code points (runes) and handles multi-byte sequences correctly. Indexing with s[i] gives you a raw byte. For most ASCII-heavy code this distinction is invisible. For internationalized text, it matters.

Go strings are immutable. Converting to []byte copies the underlying data.

Rust: Two Types, One Truth

Rust draws a sharp line between owned and borrowed strings.

String is a heap-allocated, growable, UTF-8 byte buffer. It holds three things on the stack: a pointer to heap data, the current length in bytes, and the allocated capacity. It looks like a Vec<u8> that happens to be required to be valid UTF-8.

&str is a borrowed slice into UTF-8 data. Two words on the stack: a pointer and a length. No ownership, no capacity. String literals are &str pointing into read-only program memory.

Rust String (stack portion):

┌──────────────────┐
│  ptr *u8         │──→ heap: [h][e][l][l][o]
├──────────────────┤
│  len: usize = 5  │
├──────────────────┤
│  cap: usize = 8  │
└──────────────────┘

Rust &str (fat pointer):

┌──────────────────┐
│  ptr *u8         │──→ (anywhere: heap, stack, static)
├──────────────────┤
│  len: usize      │
└──────────────────┘

Rust enforces UTF-8 at all entry points. You cannot construct an invalid String. Indexing into a String with s[i] is a compile error because the index would be a byte offset, which could land in the middle of a multibyte character.

The Immutability Consequence: The O(n²) Loop

Every mainstream language except Ruby treats strings as immutable. The reason is safety and shareability: multiple parts of a program can hold references to the same string without fear that someone else will change it underneath them.

Concatenating strings inside a loop with + is O(n²) time. The cost hides well. Your solution passes on the five examples. It times out on the 100k input. Your interviewer says nothing. You stare at the cursor.

Here is why. Each + allocates a new string, copies both operands into it, and abandons the old string. After k iterations building a string of total length n, you have copied characters 1, then 2, then 3, ..., then n times. The sum 1 + 2 + ... + n is n(n+1)/2. That is O(n²).

# O(n²), DO NOT DO THIS
result = ""
for word in words:
    result += word  # New allocation + copy on every iteration

# O(n), correct approach
result = "".join(words)  # One allocation, one pass

The fix in every language: collect into a mutable buffer and join at the end. Python uses "".join(). Java and Kotlin use StringBuilder. Go uses strings.Builder. C# uses StringBuilder. JavaScript uses an array and .join("").

Python's "".join(words) is O(n) because it makes exactly one pass to measure total length, allocates once, then copies each source string in.

Each + creates a new allocation and copies everything. The total work is 1+2+3+...+n. That is n(n+1)/2. That is O(n²). The green bar at the bottom is what using a builder looks like.

Core Operations

The frequency count space complexity surprises people. If you know your alphabet is lowercase English letters, your hash map has at most 26 keys regardless of input length. O(1) space. If you allow arbitrary Unicode, it becomes O(k) where k is the number of distinct characters, but in practice k is bounded by the character set size.

Implementations

These implementations all solve the canonical string interview problem: given a string, find the length of the longest substring with no repeating characters. This is LeetCode 3 and the cleanest demonstration of the sliding window pattern. The same algorithm in every language you might reasonably encounter in an interview, plus a few you definitely will not.

def length_of_longest_substring(s: str) -> int:
    seen = {}
    left = 0
    result = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        result = max(result, right - left + 1)

    return result

What Problems Strings Solve

Strings are not usually a choice you make. They are the input. The question is which algorithm family maps to the problem you see.

Pattern matching in text covers every grep, every search box, every log parser. Naive O(n×m) search is fine for small inputs. KMP and Rabin-Karp push this to O(n+m) for large-scale work.

Parsing structured input (JSON, expression evaluators, URL routers) means character-by-character iteration, sometimes with a stack to track nesting depth.

Character frequency analysis is the backbone of anagram detection, character rearrangement, and counting distinct characters in a window. A frequency array of size 26 (or 128 for ASCII) handles the whole alphabet in constant space.

"Longest substring where X holds" is a sliding window. "Find all substrings matching a pattern" adds a frequency comparison on top. When you see either phrasing, you are looking at a substring search with constraints problem.

Palindrome detection uses two pointers from both ends, or expand-from-center for palindromic substrings.

Recognizing String Interview Patterns

The signal that a string problem wants a sliding window: the problem asks about a contiguous substring and some property that can be maintained incrementally as the window expands and contracts. If you can write "add the new right character, remove the old left character" as O(1) operations on your state, you have a sliding window.

The signal that a string problem wants two pointers: the problem asks about a pair of positions, usually from opposite ends (palindrome check, reverse in place) or moving in the same direction at different speeds.

Worked Example 1: Minimum Window Substring

The key insight: each character enters the window once (when right advances) and leaves once (when left advances). Two passes total. O(n).

Problem: given strings s and t, find the minimum-length window in s that contains all characters of t.

Why sliding window: you need a contiguous substring. The constraint ("contains all of t") can be maintained as a count: track how many characters of t are currently satisfied in the window. Expanding right adds a character. If the character is needed, increment the satisfied count. Contracting left removes a character. If that character was needed, decrement the satisfied count. Both are O(1). So the whole thing is O(n + m).

Window state for t = "ABC":
need = {A:1, B:1, C:1}, satisfied = 0

s:  A  D  O  B  E  C  O  D  E  B  A  N  C
    ↑
    right moves right until satisfied == 3 (all of t covered)
    then left moves right to shrink window
    record minimum window size each time satisfied == 3

The answer is O(n) time, O(|t|) space for the frequency maps.

Worked Example 2: Valid Palindrome with Filtering

Problem: given a string, determine if it is a palindrome after removing all non-alphanumeric characters and ignoring case.

Why two pointers: palindrome problems have natural symmetry. Left and right pointers move toward each other, skipping invalid characters. The structure of the problem (symmetric comparison from both ends) directly suggests the pointer directions.

s = "A man, a plan, a canal: Panama"

left = 0          right = len(s) - 1
↓                 ↓
A man, a plan, a canal: Panama
↓                               ↓
(skip non-alpha on each side, compare lowercase)

'a' == 'a'  → advance both
'm' == 'm'  → advance both
...

Both pointers together traverse the string once. O(n) time, O(1) space.

Reading the Signals

One clarifying question changes everything: "Can the string contain Unicode or only ASCII?" Before you write a single line of code. That question determines whether .length in JavaScript is safe, whether indexing by bytes is correct in Go, and whether your frequency array needs 26 slots or 128 or more. It also tells you whether the interviewer has a flag emoji test case waiting for you.

Recap

• Strings are immutable in almost every language. Modification creates a new object.
• Concatenating in a loop is O(n²). Use a mutable builder or join.
• Python picks its internal encoding (1, 2, or 4 bytes per char) based on the max character in the string. One emoji upgrades everything.
• Java 9+ stores Latin-1 strings in one byte per char, halving heap usage for typical application strings.
• JavaScript .length counts UTF-16 code units, not characters. Emoji have .length of 2.
• Go len(s) is byte count. for range gives runes. C strlen is O(n).
• Rust enforces valid UTF-8 at all boundaries. String owns, &str borrows.
• The sliding window cuts "longest substring satisfying X" from O(n²) to O(n).
• The two-pointer technique cuts palindrome and pair problems from O(n²) to O(n).
• Character frequency arrays are O(1) space for fixed alphabets, not O(n).
• Always ask about character set in interviews. It changes every complexity analysis.

Strings show up in every technical interview, and interviewers know candidates underestimate them. If you want to practice actually explaining these trade-offs out loud under pressure, not just writing the code, SpaceComplexity runs voice-based mock interviews where you have to narrate your reasoning as you go. The sliding window is a favorite follow-up target.

If you are building up your pattern library before interview season, the sliding window algorithm post covers the technique from first principles, and dynamic programming as recursion with memory gives you the other major optimization pattern that string problems reach for.

Further Reading

• PEP 393: Flexible String Representation: the Python proposal that introduced variable-width internal encoding
• JEP 254: Compact Strings: the Java 9 redesign that halved String memory for Latin-1 content
• JavaScript's internal character encoding: UCS-2 or UTF-16?: Mathias Bynens on surrogate pairs and .length surprises
• String (Wikipedia): history and formal definitions
• String cheatsheet for coding interviews: Tech Interview Handbook's complexity reference
• GeeksforGeeks: Longest Substring Without Repeating Characters: worked analysis of the canonical sliding window problem