Skip to content
Data Structures & Algorithms

Strings interview questions and answers

50 questions, 31 with code. About 3 h 52 min to read them all.

By TestLab · Updated

Plan for an interview
50 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a string in a data structure?

A string is a finite sequence of characters or encoded units treated as a single data value. In data structures, it is a sequence abstraction whose exact representation and available operations depend on the programming language and encoding.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concept

A string commonly supports operations such as accessing an element by position, finding its length, searching, comparing, concatenating, and creating substrings. An empty string is valid and has length zero.

Many common implementations store elements in contiguous memory, allowing constant-time indexed access. However, contiguous storage is an implementation choice rather than a requirement of the abstract string data type. A text string may contain characters or Unicode code points, while a byte string contains octets.

Python String Representation

Python 3.12’s str type represents Unicode text and is immutable. Consequently, an assignment such as message[0] = "H" raises TypeError. A changed value must be created explicitly, for example with message = "H" + message[1:].

Python’s len() counts Unicode code points, not user-perceived characters or grapheme clusters. For example, precomposed "é" contains one code point, while decomposed "e\u0301" contains two. Unicode encoding is a separate concern: it maps Unicode text to a byte representation such as UTF-8.

For byte-oriented data, Python provides bytes and bytearray. A bytes value is immutable, while a bytearray is mutable. Indexing bytes or bytearray produces an integer byte value, whereas indexing str produces a one-character string.

Complexity

Let n and m be the lengths of two strings, k be a slice’s length, L be the total number of characters being joined, and p be the number of parts.

The table’s space values include auxiliary allocations and newly created results, but exclude the source input itself. The source inputs still occupy O(n) or O(n+m) storage. No recursion is involved, so recursion-stack space is O(1).

Operation Time Space Reason
Read s[index] O(1) O(1) A supported random-access representation retrieves the element directly
Get len(s) O(1) O(1) The length is maintained as metadata
Compare strings O(n) worst case O(1) Equal-length strings may require every element to be compared
Straightforward substring search O(nm) O(1) Up to m elements may be checked at each possible starting position
Concatenate s + t O(n + m) O(n + m) A new immutable result containing both strings is created
Slice s[start:end] O(k) O(k) Slicing copies the selected elements
Build and join p parts O(L + p) O(L + p) The list stores p references and the result stores L characters

Immutability and Performance

Because strings are immutable, repeatedly modifying one can be expensive. A loop using result += piece can repeatedly copy the growing string, resulting in O(n²) behavior in the general case for a total of n characters.

A better approach is to collect the pieces in a list and call " ".join(parts) once. Building the list and joining it takes O(L + p) time and O(L + p) additional space, including the list and final result. If the list already exists, the join operation alone takes O(L) time and creates an O(L)-space result.

Slicing also creates an independent copy: text[2:6] is not a view into the original string.

When to Use a String

  • Text processing: Use str for human-readable Unicode text.

  • Identifiers and protocols: Use strings for names, keys, URLs, JSON fields, and command-line arguments.

  • Binary data: Use bytes rather than str for images, compressed content, network packets, and other non-text data.

  • Mutable character data: Use bytearray, a list of characters, or another mutable collection when frequent in-place changes are required.

Common Pitfalls

  • Confusing characters and bytes: str stores Unicode text, while bytes stores octets and has different indexing behavior.

  • Ignoring Unicode normalization: Canonically equivalent text can have different code-point sequences and therefore different lengths.

  • Assuming substrings are views: Python slicing copies data and costs O(k) time and space.

  • Repeatedly concatenating in a loop: Build a list and use join to avoid potentially quadratic copying.

  • Using list.pop(0) or list.insert(0, value): Both shift the remaining elements and take O(n) time per operation. Use collections.deque when efficient front insertion or removal is required.

2

How do strings and character arrays differ?

Strings are immutable, object-level sequences of characters, whereas character arrays are mutable, element-level sequences of characters that can be modified in place.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Definitions

  • String: A read-only sequence of characters treated as a single value. In Python 3.12, str is immutable and represents Unicode code points. Raw byte sequences must be represented by bytes/bytearray with an explicit encoding.

  • Character Array: In Python 3.12 the practical equivalent for in-place character edits is a list of single-character str objects, or a bytearray when strictly working with byte values. Each element can be accessed and reassigned independently. Treat these as different tools depending on whether you need Unicode code points or bytes.

Core Differences

Aspect String (str) Character Array (list of chars or bytearray)
Mutability Immutable. Any modification creates a new str object. Mutable. Elements can be reassigned/added/removed in place for the container (semantics differ for bytearray vs list).
Modification Index assignment (e.g. s[0] = 'x') raises a TypeError. Direct index assignment is allowed where the container is mutable.
Memory Behavior Slicing creates a copy of the selected substring. Repeated += in a loop creates intermediate str objects (costly for large n). Edits to existing elements do not require rebuilding the entire sequence to change those elements, but creating a new list by slicing or ''.join() still allocates new objects.
Identity vs Value Often treated by value for equality (== compares the character/code-point sequence). A mutable container: identity differs from another object even if element sequences are equal; compare elements explicitly.
Unicode Awareness len(s) counts Unicode code points. Indexing returns a str for that code point. Use ord() and chr() for character arithmetic. With a list of single-character str, the same Unicode code-point rule applies per element. With bytearray, you are dealing with byte values only — you must decode/encode with an explicit encoding and cannot assume 1 code point per byte.
Intended Use Best for fixed textual data, keys/lookups, or values that must not be accidentally mutated. Best for in-place transformations (swaps/reversals/permutations) where you intend to mutate elements before producing a final str with ''.join().

Complexity Notes

Apply the following to Python 3.12 for the operations most relevant to this distinction. “Input counted” here means: is the original input sequence counted in the stated space complexity (total) or is space counted as auxiliary/extras beyond the input?

Operation Time (Big-O) Space (Big-O) Notes
String slicing s[i:j] O(k) where k = j-i (best/avg/worst same here) O(k). Input counted: yes for total if you count the new substring as output derived from input; treat as O(k) for the copy created. Creates a new str copy of those code points.
s += c inside a loop (n appends) O(n^2) in the worst/typical case for naive str concatenation in CPython (best case rare). Reason: str is immutable so each += may copy the entire current string to form a new one. O(n) for the final string objects created over time. Input counted: the growing result is counted in total space; auxiliary copies are the cost. Avoid in loops; prefer list + ''.join().
lst.append(c) / element reassignment in a list O(1) amortized for append in the common case (worst case reallocation; say “amortized” where reallocation happens). Element assignment lst[i] = c is O(1). O(1) auxiliary for the assignment/append action beyond the list storage; Input counted: the list elements are the working copy (if built from input) — state auxiliary vs total per use. Amortized applies to dynamic array growth (append).
Build from list + ''.join(lst) O(M) where M is the total number of characters/code points in the joined sequence (best/avg/worst typically O(M), linear). O(M) for the result str and the list of parts. Input counted: count the final string as output; the list is working storage derived from/for the input. Preferred for many concatenations; do not rely on list.pop(0) or list.insert(0, x) in loops (O(t) per operation).

Practical Implications

  • Transformations: To reverse a string in-place in effect, convert str to a mutable container (e.g. a list of single-character str), perform swaps, then ''.join() to produce a new str (the original str remains immutable).

  • Building Results: For building a large sequence over many iterations, use a list and ''.join() at the end rather than s += c in a loop.

  • Character Semantics: Unless explicitly stated, do not assume lowercase ASCII. Be explicit about Unicode code points vs bytes: use ord()/chr() intentionally, and only convert between bytes/str with an explicit encoding/decoding.

Edge Cases to Consider

  • Empty input: An empty str and an empty mutable container both have length 0, but mutability and allowed operations still differ.

  • One element: Mutability is the distinction even for length 1.

  • Duplicates: Affect equality, hashing keys and frequency-based logic regardless of representation.

  • Unicode characters: A human “character” may be a code point; len() counts code points. With bytearray there is no code-point guarantee.

  • Already “finalized” text: Treating text as immutable prevents accidental cross-reference mutation; converting to a mutable container creates a copy/workspace and does not retroactively change other references to the original str.

Common Pitfalls

  • Mutating a string: Attempting index assignment to a str raises a TypeError. Convert to a mutable container first if mutation is required.

  • Counting bytes instead of code points: Using len() without considering Unicode can be misleading. Use ord()/chr() intentionally when doing character arithmetic.

  • Inefficient concatenation: Using s += c in a loop instead of list + ''.join() is a frequent source of O(n^2) work.

  • Mixing bytes and str: Treating a byte sequence as text (or vice versa) is an encoding error. Only convert with an explicit encoding, and prefer bytearray only when byte-level mutation is truly required.

  • Forgetting immutability in references: Multiple variables can reference the same immutable str object; mutating a copied container will not affect the original str.

  • Interview follow-ups to expect: Be ready to justify when you’d choose a mutable container over str, explain the cost of ''.join(), state whether input is counted for the space you’re quoting, and point out the difference between mutability, copying, and Unicode code points vs bytes.

3

What does a null-terminated string represent in memory?

A null-terminated string stores encoded character data followed by a null terminator, usually the byte 0x00, which marks where the string ends. The terminator is not part of the visible text; for example, "Hi" is stored in a byte buffer as H, i, 0x00.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A program reads encoded bytes or code units sequentially until it encounters the null terminator:

Stored bytes Visible text String length
72 00 H 1
72 69 00 Hi 2
00 empty string 0

The terminator distinguishes the end of the string from any bytes that follow it in memory. A byte buffer containing "Hi" needs three bytes: two for the characters and one for 0x00.

This representation is commonly used by C and C++. Functions such as strlen, printf, and strcpy rely on null-terminated strings to identify their string boundaries. The terminator itself is not included in the visible string length.

Characters Versus Bytes

A null-terminated string is fundamentally a sequence of encoded bytes or code units, not an inherent sequence of Unicode characters:

  • ASCII: Each character occupies one byte.

  • UTF-8: A Unicode code point occupies between one and four bytes. A user-visible character can require multiple code points, such as when combining marks are used.

  • UTF-16: A Unicode code point is encoded as one or two 16-bit code units, and the terminator is typically the two-byte value 0x0000.

  • Embedded nulls: A byte sequence such as A\0B appears as "A" when interpreted as a conventional null-terminated string, even though B remains in memory.

Python’s built-in str is different. It is immutable, stores Unicode content, and is not represented as a conventional null-terminated character array. Python bytes objects may contain null bytes and can be passed to C APIs that accept byte strings, but a C API will generally interpret an embedded null as the end of the string.

Complexity

For a byte-oriented null-terminated string with n bytes before the terminator:

  • Best case: O(n) because the scan must inspect all n content bytes and the terminator.

  • Average case: O(n) for the same reason.

  • Worst case: O(n) for the same reason.

  • Empty string: The check is O(1) because the first byte is already the terminator.

  • Auxiliary space: O(1) for scanning. The input is not counted as auxiliary space; it occupies n + 1 bytes in a byte-oriented representation. In a fixed-width encoding such as UTF-16, the terminator may instead require multiple bytes.

If the length is stored separately, obtaining it is O(1).

Advantages and Limitations

  • Advantages: Simple representation, easy interoperability with C-style APIs, and straightforward use with memory-copying functions.

  • Limitations: The length is not inherently known, so scanning may be necessary. Embedded null bytes cannot appear as visible content in a conventional C string.

  • Buffer safety: A string must be large enough for its content and terminator. Writing beyond the allocated buffer causes undefined behavior in C and C++.

  • Encoding: Byte length and Unicode character count are not always equal for multibyte encodings such as UTF-8.

Common Pitfalls

  • Forgetting to allocate space for the terminator.

  • Assuming the terminator is included in the visible string length.

  • Confusing byte count with Unicode character count.

  • Using strlen or similar operations on a buffer that lacks a terminator.

  • Treating embedded null bytes as ordinary visible characters.

  • Assuming Python str objects use the same representation as C strings.

A common interview follow-up asks how the length of a null-terminated string is determined when it is not stored. The answer is to scan until the null terminator, which takes O(n) time.

4

How do mutable and immutable strings differ?

Mutability determines whether a string’s existing contents can be changed after creation, while immutability means every modification produces a new string. In Python, str objects are immutable, so operations such as replacement or concatenation return new objects rather than altering the original.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

A string’s mutability is a property of its type, not of the variable that references it.

Property Mutable string Immutable string
Modify existing contents Allowed in place Not allowed
Result of an update The same object changes Usually a new object is returned
Sharing between owners Owners can observe changes Owners continue seeing the original value
Thread-safety Requires synchronization when shared and concurrently modified Safe to share because values cannot change
Use as a dictionary key Usually unsuitable if its contents affect equality Suitable when hashable
Typical example bytearray str and bytes in Python

For example, if original and reference both refer to the Python string "hello", executing reference += " world" rebinds reference to a new string. It does not modify the original string, so original still contains "hello".

How Immutability Works in Python

Python’s str represents text as a sequence of Unicode code points. Common operations therefore behave as value transformations:

  • Indexing: text[0] returns a one-code-point string.

  • Slicing: text[start:end] returns a new string.

  • Replacement: text.replace(...) returns a new string.

  • Concatenation: text + suffix returns a new string.

  • Normalization: text.lower() returns a new string.

The original object remains unchanged in every case. Other languages differ: Java’s String is immutable, while StringBuilder is mutable; C++’s std::string is mutable.

Time and Space Complexity

For a string of length n and a slice of length k, the following complexities apply. Input storage is excluded from auxiliary space unless explicitly stated.

Operation Best case Average case Worst case Extra space Reason
Access one code point O(1) O(1) O(1) O(1) A code point can be located directly
Traverse the string O(n) O(n) O(n) O(1) Every code point must be visited
Copy a slice of length k O(k) O(k) O(k) O(k) The slice and its copy contain k code points
Concatenate strings of lengths n and m O(n + m) O(n + m) O(n + m) O(n + m) A new result string must be allocated
Hash the entire string O(n) O(n) O(n) O(1) All code points must be processed

Python caches a string’s hash after its first calculation, so subsequent calls to hash(text) are O(1). The immutability of str makes this caching safe.

Practical Implications

  • Safe sharing: Immutable strings can be passed between functions or threads without one caller unexpectedly changing another caller’s value.

  • Hashability: Immutable str objects can be dictionary keys and set members.

  • Simple reasoning: A string value effectively identifies a fixed sequence rather than a changing buffer.

  • Memory awareness: Repeated transformations can create temporary strings and increase memory usage.

  • Unicode awareness: Python str stores Unicode code points, so len(text) counts code points rather than encoded bytes. A user-perceived character, such as an emoji with multiple code points, may count as more than one.

Common Pitfalls

  • Rebinding is not mutation: text = text.upper() creates a new string and rebinds text; it does not modify the old object.

  • Repeated += can be quadratic: Building a string with += in a loop may repeatedly copy the growing result, giving O(n²) time in the worst case.

  • Use join for accumulation: Collect strings in a list and call "".join(parts). For total input length L, this takes O(L) time and O(L) space for the result.

  • Do not confuse text and bytes: str represents Unicode text, bytes represents immutable byte sequences, and bytearray is a mutable byte sequence.

  • Watch slicing costs: Slicing copies k code points and requires O(k) space; it is not a view into the original string.

5

How do programming languages represent and manipulate strings?

Programming languages represent strings as sequences of encoded characters or bytes and provide operations for comparison, searching, slicing, concatenation, and encoding. The string representation—Unicode code points, UTF-16 code units, or raw bytes—determines indexing behavior, memory usage, and complexity.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Common Representations

Language Logical unit Mutability and encoding notes
Python 3.12 Unicode code points str is immutable; compact internal storage uses ASCII or wider Unicode representations. bytes is separate.
Java 21 UTF-16 code units String is immutable. A supplementary Unicode character, such as an emoji, occupies two char units.
JavaScript ES2023 UTF-16 code units Strings are immutable. length counts code units rather than user-perceived characters.
C++20 Bytes in std::string std::string is mutable and encoding-agnostic. std::u16string and std::u32string provide UTF-specific alternatives.

Internally, runtimes may use contiguous byte buffers, compact encodings, or tree-like structures such as ropes. These details affect performance but should not normally change observable behavior.

Characters, Code Units, and Bytes

A character is not represented identically everywhere:

  • Unicode code point: One value in the Unicode standard. In Python 3.12, len(str) counts code points.

  • UTF-16 code unit: A 16-bit value used by Java and JavaScript. Some characters require two units.

  • Byte: An 8-bit value. UTF-8 uses between one and four bytes per code point.

  • User-perceived character: What a reader considers one letter or symbol. It may consist of several code points.

For example, in text that contains "é", the number of code points, UTF-16 code units, and UTF-8 bytes can all differ depending on the encoding and representation used. Unicode normalization also matters: visually identical text can have different encodings. Python does not automatically normalize strings, so comparisons may require unicodedata.normalize() when the data producer does not guarantee a canonical form.

Operation Costs

Let n be the input length and k the length of a selected substring. Space complexity here is stated as auxiliary space excluding the input unless explicitly stated.

Operation Time complexity Space complexity Reason
Access by a direct index to the representation’s fixed unit O(1) best/average/worst O(1) auxiliary (input not counted) Only applies when units are fixed-width and directly addressable. For variable-width encodings (e.g. UTF-8) finding a specific code point by character index can require scanning and is not guaranteed O(1).
Iterate over all represented units O(n) best/average/worst O(1) auxiliary (input not counted) Every represented unit is visited once.
Slice or extract a substring O(k) best/average/worst O(k) auxiliary for the new copy/output (input not counted) With immutable strings, creating the selected substring produces a copy of those k units.
Concatenate two immutable strings O(n + m) best/average/worst O(n + m) auxiliary for the new string (input not counted) A new string must contain both operands.
Encode or decode text O(n) best/average/worst O(n) auxiliary for the encoded/decoded output (input not counted) The complete input is converted.
Append to a mutable builder O(1) amortized O(n) auxiliary for the buffer over time (input not counted) Occasional buffer growth copies existing content.

These costs describe the logical operation. Particular runtimes may optimize concatenation or searching internally, but for immutable strings slicing still creates a copy.

Construction and Manipulation

  • Immutable strings: Operations return new objects. This simplifies sharing, caching, and safe use as dictionary keys.

  • Mutable buffers: StringBuilder in Java, StringBuffer in older APIs, and similar builders in other languages reduce repeated copying when constructing large strings.

  • Python concatenation: Repeated result += part inside a loop can take O(n²) total time because intermediate immutable strings are copied. Collect parts in a list and call "".join(parts) for linear construction.

  • Search and comparison: Built-in APIs are usually optimized and may use linear-time or pattern-based algorithms. Complexity therefore depends on the language and implementation rather than only on the source expression.

  • Unicode-aware APIs: Prefer casefold() over lower() for caseless comparisons, because Unicode case conversion can change text length and produce multiple characters.

Common Pitfalls

  • Confusing code points, code units, and bytes: Check what the language’s length property actually counts.

  • Assuming UTF-8 means one byte per character: Non-ASCII characters commonly require multiple bytes.

  • Ignoring Unicode normalization: Visually equal strings may not compare equal.

  • Repeated immutable concatenation: Use a builder or join rather than += in a Python loop.

  • Forgetting that slicing copies: Slicing an immutable string consumes time and space proportional to the copied length.

  • Off-by-one errors: Carefully define whether substring and range endpoints are inclusive or exclusive.

  • Integer overflow: In fixed-width languages, expressions such as left + right or n + m can overflow when calculating buffer sizes.

  • Unexpected mutation: Some C++ and buffer APIs modify their inputs, while Python, Java, and JavaScript string operations normally return new values.

Interviewers commonly follow up by asking how len() differs between bytes and text, why immutable concatenation can be expensive, or how UTF-8 handles characters outside the ASCII range.

6

Do character arrays improve password security compared with Strings?

Character arrays can improve password security over immutable Strings because a mutable buffer can be overwritten before it is discarded. This provides better control over sensitive data, but it is defense in depth rather than a guarantee of secure memory handling.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Security Difference

Immutable String objects cannot be changed after creation. A password stored in a String may therefore remain in memory until it is garbage-collected, and temporary copies created during formatting, logging, or serialization may remain longer.

A mutable character array, such as Java’s char[] or .NET’s char[], can instead be cleared before it is discarded:

  • Overwrite every element with its zero value.

  • Drop the reference to the buffer afterward.

  • Avoid unnecessary copies while the password is being used.

In Python 3.12, the closest mutable byte-oriented equivalent is bytearray; both str and bytes are immutable. Converting an existing str or bytes value to bytearray creates a mutable copy but does not erase the original immutable object. A mutable buffer therefore improves erasure only when the password can be obtained without first creating an unnecessary immutable copy.

Time and Space Complexity

Let n be the number of characters or bytes in the password.

Operation Best, Average and Worst Time Space Reason
Copying a password into a mutable buffer O(n) O(n) Every character or byte is copied
Clearing a mutable buffer O(n) O(1) auxiliary Every position is overwritten once
Creating an immutable string O(n) O(n) A new object and its character storage are required
Processing the input for a password hash O(n) for input scanning O(n) plus algorithm-dependent working memory The password must be read; the algorithm’s configured work factor and memory use determine the total cost

The table counts the destination or hashing-input buffer but not an already-existing source secret. Total password-hashing time is not necessarily O(n) because algorithms such as Argon2id, bcrypt, scrypt, and PBKDF2 deliberately include additional work.

Limitations and Caveats

  • Mutable does not mean automatically secure: The application must clear the array promptly and correctly.

  • Copies may survive: Logging, formatting, GUI components, serialization, exceptions, and temporary conversions can create copies that cannot be cleared.

  • Runtime behavior varies: Compilers, just-in-time runtimes, and garbage collectors may move, copy, or retain objects, so explicit zeroization is stronger but not a universal guarantee.

  • Storage is a separate concern: A character array addresses transient memory; it does not define how a password should be stored permanently.

  • Password hashing is still required: For persistent storage, use a salted, adaptive password hash such as Argon2id, bcrypt, scrypt, or PBKDF2 with appropriate parameters—not raw characters or an unsalted fast hash.

Best Practices

  • Minimize the password’s lifetime and the number of copies created.

  • When the platform supports it, use a mutable buffer and clear it in a finally block or equivalent cleanup path.

  • If an API requires an immutable string, use it only for as short a period as possible and never log it.

  • Do not assume converting a secret to bytearray erases a previously created str or bytes copy.

  • Use a reputable password-hashing library when storing passwords.

  • Treat zeroization as defense in depth rather than a substitute for secure coding and storage controls.

Common Pitfalls

  • Assuming that deleting a String immediately removes its contents from memory.

  • Clearing only the original array while leaving copies in logs, exceptions, or temporary objects.

  • Converting an immutable password to a mutable buffer while overlooking the original copy.

  • Using a character array as the permanent storage format for passwords.

  • Assuming every runtime guarantees that a compiler or garbage collector will erase secret memory promptly.

  • Forgetting that Java char[] stores UTF-16 code units, while Python str represents Unicode code points; use the platform’s documented encoding rules when comparing or transferring passwords.

7

How does indexing work in Python string operations?

In Python 3.12, string indexing is zero-based and returns the character at a specified position, where each position represents one Unicode code point rather than necessarily one user-perceived character. Indexing supports fast direct access, but slicing and many whole-string operations create or scan new data, so their complexity depends on the operation and string length.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Indexing Model

Python strings are immutable and indexed with square brackets:

text = "Python"

text[0]     # 'P'
text[3]     # 'h'
text[-1]    # 'n'
  • Zero-based indexing: The first character is at index 0.

  • Negative indexing: -1 refers to the final character, -2 to the second-to-last, and so on.

  • Bounds checking: An out-of-range index raises IndexError.

  • Immutability: Individual characters cannot be assigned, so text[0] = "J" raises TypeError.

  • Unicode code points: len counts code points, not bytes or grapheme clusters. For example, "é" has length 1, while "e\u0301" has length 2 because it contains two code points.

For text = "café":

Index Character
0 c
1 a
2 f
3 é

bytes behave differently: indexing a bytes object returns an integer byte value, not a character, and len(bytes) counts bytes.

Effects on Common Operations

Indexing is especially useful when an algorithm needs to compare positions directly:

  • Two-pointer algorithms: Palindrome checks compare text[left] with text[right] while moving the pointers inward.

  • Sliding windows: A window is commonly represented by two indices, such as text[left:right + 1].

  • Character classification: ord(text[index]) obtains a code point’s numeric value, while chr(value) converts it back.

  • Searching: Methods such as find return an integer index or -1; index returns an integer index but raises ValueError when no match exists.

  • Slicing: text[start:end] creates a new string, unlike direct indexing, which does not copy the entire input.

  • Concatenation: Because strings are immutable, “changing” one character generally requires constructing another string. Repeated += in a loop can become quadratic in time and use O(n) peak space; use a list and "".join(parts) for O(n) time and O(n) space.

  • Iteration: for character in text visits code points, while enumerate(text) provides both the index and character.

Complexity

These bounds assume Python 3.12’s built-in str implementation and exclude the original input from the space calculation.

Operation Best time Average time Worst time Space
text[index] O(1) O(1) O(1) O(1)
len(text) O(1) O(1) O(1) O(1)
text[start:end] O(k) O(k) O(k) O(k) including the result; O(1) auxiliary excluding it
text[::-1] O(n) O(n) O(n) O(n) including the result; O(1) auxiliary excluding it
Direct iteration O(n) O(n) O(n) O(1)
Two-pointer palindrome check O(n) O(n) O(n) O(1)

Here, n is the number of code points and k is the number of code points in the slice. The palindrome implementation below uses no recursion, so there is no recursion-stack cost.

Code Example

def is_palindrome(text: str) -> bool:
    """Check whether text is a palindrome by Unicode code point."""
    if len(text) < 2:
        return True

    # Compare the outermost pair, then move toward the center.
    left, right = 0, len(text) - 1

    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1

    return True


print(is_palindrome("level"))
# True

For "level", the algorithm proceeds as follows:

  1. left = 0 and right = 4; compare l with l.

  2. left = 1 and right = 3; compare e with e.

  3. The pointers meet in the middle, so return True.

It handles empty strings and one-character strings, which are palindromes.

Common Pitfalls

  • Confusing code points with user-perceived characters: A family emoji or combining-character sequence may contain several code points, so this algorithm checks code-point symmetry rather than grapheme-cluster symmetry.

  • Assuming normalization changes case: "Level" and "level" remain different after Unicode normalization. Use casefold() or lower() for case-insensitive comparison, and strip() when surrounding whitespace should be removed.

  • Forgetting immutability: Do not attempt text[index] = value; create a modified string instead.

  • Using += inside a loop: Repeated concatenation can take O(n²) time. Collect fragments in a list and call "".join(parts).

  • Assuming slicing is free: A slice copies the selected code points and uses O(k) space for the result.

  • Overlooking index errors: Empty strings have no valid character index, and direct indexing must be bounds-checked when the input is user-controlled.

  • Likely interview follow-up: Ask how the same operations differ for bytes, non-ASCII text, and grapheme-cluster-aware processing.

8

What is a Pascal string in string handling?

A Pascal string is a length-prefixed string: one or more bytes store the string’s length before the character data. Unlike a null-terminated C string, it does not require a trailing \0, and the length can be obtained directly from the prefix.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Format

A traditional Pascal string uses a single-byte unsigned length prefix, so its maximum payload length is 255 bytes. Its structure is [length byte][character data].

For example, the five-character ASCII string Hello is represented by the bytes 05 48 65 6C 6C 6F:

  • 05 is the unsigned payload length in bytes.

  • 48 65 6C 6C 6F contains the bytes for Hello.

  • No null terminator is required because the prefix identifies the payload’s end.

Why Length Prefixes Are Used

  • Fast length lookup: The number of bytes or other encoded units can be read without scanning the payload.

  • No terminator scanning: Finding the end does not require comparing every character with \0.

  • Binary-safe payloads: Embedded null bytes can be handled as ordinary data when the format permits them.

  • Easy serialization: Length and data can be written together without relying on a language-specific string representation.

Length-prefixed strings are useful in file formats, network protocols, serialized objects, and interfaces where strings cross language or system boundaries.

Relation to Pascal

The term commonly describes the Pascal-style length-prefixed representation, not necessarily every string type in every Pascal compiler.

In traditional Pascal implementations such as Turbo Pascal, a fixed-length string buffer reserves its first byte for the current length and permits at most 255 characters. Modern Pascal dialects may instead provide dynamically sized strings, length-prefixed records, or compiler-specific representations. For interoperability, Pascal-style length-prefixed string is therefore more precise than assuming every Pascal string has the same representation.

Complexity

Let n be the payload length in bytes or other stored code units. Assume a fixed-width prefix and contiguous storage. The best, average, and worst-case algorithmic times are the same for these operations.

Operation Time Space Reason
Read the length O(1) O(1) auxiliary A fixed-width prefix stores the length directly.
Access a stored byte or code unit by index O(1) O(1) auxiliary Direct indexing is supported by contiguous storage.
Traverse the payload O(n) O(1) auxiliary, excluding input Every payload unit must be visited.
Copy or extract the payload O(n) O(n) for the new output, excluding input All n units must be copied.
Store a complete string O(n) O(n + 1) total storage Storage is needed for the prefix and payload.

The auxiliary-space figures exclude the input and any returned output. In Python 3.12, slicing bytes creates a copy, so extracting the payload requires O(n) time and O(n) additional space.

Character Versus Byte Length

The prefix in the classic format counts bytes, not Unicode code points. For example, é uses two bytes in UTF-8 but is one Unicode code point. Python’s bytes length therefore matches the prefix count, while str length may not.

Use a UTF-8 byte length when serializing: "é" is one code point and two UTF-8 bytes. Always specify whether a length represents bytes or characters when designing a format. A four-byte prefix can support larger values, but its byte order and integer encoding must also be defined.

Common Pitfalls

  • Confusing Pascal with the format: Compiler-specific Pascal string types do not all use the same representation.

  • Ignoring the length limit: A one-byte prefix represents lengths from 0 through 255, but not larger values.

  • Handling the empty string: A zero-length payload is valid and is represented by a prefix of 0.

  • Assuming null termination: Searching for \0 as the string boundary is incorrect for a length-prefixed value.

  • Mixing bytes and characters: UTF-8 character count and encoded byte count differ for non-ASCII text.

  • Changing the prefix convention: Receivers must agree on prefix size, byte order for multi-byte prefixes, and whether the length includes the prefix itself.

  • Repeated concatenation: Building strings with += in a Python loop can become O(n²); collect fragments in a list and use ''.join() when constructing text dynamically.

9

How does string concatenation work and what is its complexity?

String concatenation combines the characters of two or more strings into a new sequence. Because Python strings are immutable, concatenation generally creates a new string; repeated concatenation can therefore be expensive unless the implementation can efficiently reuse the existing storage.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

In Python, the + operator concatenates two strings. For example, combined = left + right preserves the order of all characters from left, followed by all characters from right.

Step Result
Start with "str" "str"
Concatenate "ing" "string"
Concatenate " concat" "string concat"
Concatenate "enation" "string concatenation"

Python str objects represent sequences of Unicode code points. Therefore, len(text) counts code points, not encoded bytes. A character such as "é" occupies one position in a Python string but two bytes in UTF-8.

Concatenating a string with a non-string raises TypeError. Empty strings are valid operands, "".join([]) returns "", and duplicate parts are preserved in order.

Time and Space Complexity

Let:

  • n be the number of code points in the first string.

  • m be the number of code points in the second string.

  • q be the number of concatenation operations.

  • L be the total number of code points across all input parts.

Approach Best time Average time Worst time Space
One left + right O(1) when one operand is empty O(n + m) O(n + m) O(n + m) including the result
Repeated result = result + part O(q + L) O(qL) O(qL) O(L) including the current and new result
Repeated result += part O(q + L) amortized when storage is reused O(qL) without guaranteed reuse O(qL) O(L) including the current result
"".join(parts) O(q + L) O(q + L) O(q + L) O(q + L) including the result and temporary references

A single concatenation copies the characters into a new immutable string, except that CPython can reuse the non-empty operand when the other operand is empty. For repeated immutable concatenation, each operation may copy the entire accumulated result, so the total work can grow quadratically. When q is also Θ(L), the common worst case is O(L²).

CPython 3.12 can optimize some += patterns when it can reuse the destination’s storage, commonly for an exclusively referenced local string. This can produce an amortized O(q + L) total cost, but it is an implementation optimization rather than a portable guarantee.

The space figures include the newly created output but do not count the input strings or input collection. str.join can additionally use O(q) space for temporary references to its parts. There is no recursion stack, so its contribution is O(1).

Code Example

For multiple parts, str.join is preferred because it copies the characters into the final result once:

def concatenate_parts(parts: list[str]) -> str:
    """Join string parts in order without repeated immutable-string copying."""
    return "".join(parts)


result = concatenate_parts(["str", "ing", " concat", "enation"])
print(result)  # string concatenation

This function handles an empty list by returning "", preserves empty and duplicate parts, and returns the same content whether there is one part or many.

Best Practices

  • Use join for collections: Prefer "".join(parts) when combining an unknown number of strings.

  • Use + for a small fixed number of operands: A few direct concatenations are straightforward and generally efficient.

  • Avoid repeated += in loops: Although CPython may optimize some cases, repeated immutable-string concatenation can become O(L²).

  • Use str.join or io.StringIO for generated output: Both avoid repeatedly copying the entire accumulated result.

  • Count characters, not bytes: Python string complexity is usually measured in code points; encoded byte length depends on the encoding.

  • Remember that slicing copies: Extracting a substring with text[start:end] creates a new string and costs O(end - start) time and space.

Common Pitfalls

  • Assuming += is always constant-time because it resembles an append operation.

  • Ignoring quadratic copying when building a large string inside a loop.

  • Measuring UTF-8 byte size with len(text); len counts Unicode code points.

  • Forgetting to include output storage and temporary references when discussing space complexity.

  • Assuming empty parts or duplicate parts are removed—concatenation preserves them exactly.

  • Mutating strings character by character, which is impossible because Python strings are immutable.

10

What is the time complexity of substring search in strings?

Substring search has no single time complexity: it depends on the matching algorithm. A naive search takes O(n × m) time in the worst case, while an optimal algorithm such as KMP takes O(n + m) time by avoiding repeated comparisons after a mismatch.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let:

  • n be the length of the text.

  • m be the length of the pattern.

A naive algorithm checks the pattern at every possible text position. Each alignment can require up to m character comparisons, giving O(n × m) worst-case time.

KMP uses a prefix function to determine how much of the pattern can be reused after a mismatch:

  • prefix[i] is the length of the longest proper prefix of pattern[:i + 1] that is also a suffix.

  • After a mismatch, the algorithm falls back to a valid shorter prefix instead of restarting the comparison.

  • Although an individual pattern character may be reconsidered after a failure, the total number of comparisons is amortized linear, producing O(n + m) time.

For example, searching for "ABABC" in "ABABABC":

  1. The alignment starting at index 0 matches "ABAB".

  2. At index 4, the text character A mismatches the pattern character C.

  3. The prefix function identifies "AB" as the reusable prefix and suffix, so the search falls back to that alignment.

  4. The pattern then matches from index 2 through index 6.

Complexity Comparison

Approach Best case Average case Worst case Auxiliary space
Naive search O(n) Distribution-dependent; O(n) for i.i.d. random characters O(n × m) O(1)
KMP O(n + m) O(n + m) O(n + m) O(m)
Rabin–Karp with hashing and verification O(n + m) Expected O(n + m) with a suitable random hash O(n × m) with adversarial collisions O(1)
  • KMP time: O(n + m) because prefix-function construction takes O(m) and scanning the text takes O(n).

  • KMP space: O(m) for the prefix table, excluding the input strings.

  • Naive space: O(1) auxiliary space for indices and a comparison counter.

  • Rabin–Karp space: O(1) auxiliary space for a rolling hash, excluding the inputs and any sliced result.

Python 3.12’s built-in in operator and str.find() use optimized implementations, but Python does not specify one universal time-complexity guarantee for them across all implementations.

Edge Cases

  • Empty pattern: By the usual convention, it matches at position 0 with a zero-length result.

  • Empty text: A nonempty pattern cannot match; an empty pattern still matches at position 0.

  • Pattern longer than the text: No match is possible.

  • One-element input: A match occurs only when the text and pattern contain the same character.

  • Duplicate occurrences: Searching for the first occurrence stops at its earliest starting position.

  • Unicode: Python strings represent Unicode code points, and len() counts code points. KMP compares code points rather than encoded bytes.

Common Pitfalls

  • Do not describe every substring search as O(n × m); that is the naive worst-case bound, not the optimal one.

  • Include pattern preprocessing in KMP’s analysis: it uses O(m) time and space in addition to scanning the text.

  • Do not claim a universal average case for naive search without specifying the input distribution.

  • Slicing text[start:end] creates an O(k) copy; returning indices avoids that output allocation.

  • Do not modify the input strings during the search; Python strings are immutable.

  • For byte-oriented data, use bytes or bytearray; their indexes represent bytes rather than Unicode code points.

11

How does a rope data structure organize large strings?

A rope is a tree-based data structure for storing and manipulating large strings or character sequences. Instead of copying all characters during every concatenation, it stores text in chunks connected by internal concatenation nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Representation

A rope is commonly implemented as a balanced tree:

  • Leaf nodes contain chunks of characters rather than necessarily storing one character per node.

  • Internal nodes represent the concatenation of their children.

  • Balancing keeps the height small, typically O(log n) for a balanced rope with n characters.

  • Weights or lengths stored at nodes let the implementation locate characters without scanning every preceding character.

For example, a rope representing "Hello, world!" might initially have one leaf. Concatenating it with " Welcome" can create another leaf and an internal parent without copying either original chunk.

Why It Exists

Python strings are immutable. Repeatedly executing text += "more" in a loop can therefore copy the growing string repeatedly, resulting in O(n²) total time in the worst case. A rope represents edits through small tree nodes and references, reducing copying.

Ropes are useful in editors, document-processing systems, and text buffers that perform many insertions, deletions, concatenations, or substring operations on large text.

Core Operations and Complexity

Let n be the total number of characters, k the length of a materialized substring, c the number of characters in a leaf chunk, h the tree height, and m the number of leaves. Space below is additional to the stored rope unless an output is explicitly noted.

Operation Time Additional space
Link two existing roots O(1) O(1)
Locate a character O(h + c) O(1)
Insert or delete using path copying and chunk splitting O(h + c) O(h + c)
Materialize a substring as a flat sequence O(h + c + k) O(k) output plus O(h) auxiliary space
Create a structural substring sharing existing chunks O(h) O(h)
Visit every character O(n) O(h) auxiliary space for an iterative traversal
Visit only chunk nodes O(m) O(h) auxiliary space
  • Best, average, and worst case with a maintained balanced invariant: indexed lookup and bounded-chunk edits are O(log n + c), including when c is constant.

  • Worst case with a degenerate tree: height can become O(n), making lookup and edits O(n + c).

  • Concatenation: creating the parent reference is always O(1). Maintaining the balance invariant is implementation-dependent; a straightforward full rebuild of m leaves takes O(m) time and O(m) space.

  • A flat substring must copy k characters, while a structural substring can share chunks and avoid that O(k) copy.

Including character storage and node metadata, a rope occupies O(n + m) = O(n) space.

Example Walkthrough

Suppose two ropes contain "Hello" and " world".

  1. Each chunk is stored in a leaf node.

  2. Concatenation creates an internal node referencing both leaves.

  3. The root stores the combined length, 11.

  4. Accessing index 6 follows subtree lengths to the second leaf and then scans within that leaf.

  5. Inserting "there" splits or updates the affected leaf and reconnects the relevant ancestors.

The original chunks do not need to be copied merely to represent their concatenation.

Advantages and Limitations

  • Advantages: Fast structural concatenation, efficient indexed access, and reduced copying during edits.

  • Limitations: More metadata than a flat string, a more complicated implementation, and balancing costs.

  • A rope is most beneficial for large, frequently edited text; short strings or strings with few edits are usually simpler and faster as flat immutable strings.

  • Ropes operate on characters, not necessarily bytes. Python’s len counts Unicode code points, whereas a byte-oriented implementation indexes bytes.

Common Pitfalls and Interview Tips

  • Do not claim that every rope operation is O(1); only linking two existing roots is inherently constant-time.

  • Account for scanning within a multi-character leaf when discussing indexed lookup.

  • Distinguish a copied flat substring from a structural substring that shares chunks.

  • Mention that balancing is essential for logarithmic lookup performance.

  • Python’s standard library does not expose a built-in rope implementation; list followed by ''.join(...) is the usual way to avoid quadratic immutable-string concatenation.

  • Common follow-ups ask about balancing, locating characters, sharing nodes during edits, and comparing ropes with immutable strings or gap buffers.

12

What are the key advantages and limitations of ropes?

A rope is a tree-based data structure for representing strings as a sequence of smaller string chunks. It is especially useful when large strings are repeatedly concatenated, split, or edited, because it can avoid copying the entire string for every operation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Ropes Work

A rope typically has:

  • Leaf nodes: Contain small chunks of text.

  • Internal nodes: Represent concatenation and are usually kept balanced.

  • Structural sharing: Multiple ropes can refer to the same unchanged chunks.

For example, concatenating "hello" and "world" can create a new internal node pointing to the two existing chunks instead of copying all characters into a new string. Python’s built-in str does not provide this behavior directly; rope implementations are generally provided by specialized libraries or custom code.

Key Advantages

  • Efficient concatenation: Joining two balanced ropes generally requires logarithmic tree work rather than copying all characters.

  • Efficient splitting: A rope can be divided at a position without duplicating the unchanged portions.

  • Localized updates: Editing one section can create new nodes along the path to that section while sharing the rest.

  • Good fit for large documents: Text editors, compilers, and version-control systems often need to manipulate large strings incrementally.

  • Persistent or copy-on-write designs: Existing rope versions can remain unchanged while a new version shares most of their structure.

  • Flexible chunking: Chunks can be split, combined, compressed, or sourced from different storage mechanisms.

Limitations

  • Higher memory overhead: Every chunk and internal node requires metadata, so a rope can use more memory than a flat string.

  • Slower random access: Finding an individual character usually requires traversing the tree, whereas indexing a Python str is effectively constant time.

  • More complex implementation: Balancing, sharing, splitting, and garbage collection are substantially harder to implement correctly than ordinary string concatenation.

  • Small-string overhead: For short strings or applications dominated by ordinary operations, a flat string is often simpler and faster.

  • Mutation costs depend on the design: In a persistent rope, each edit may allocate new nodes. In a mutable rope, updates can be cheaper but may reduce the benefits of version sharing.

  • Unicode and encoding complexity: Chunks must respect the intended character or byte boundaries. Python strings represent Unicode code points, while byte-oriented languages may use different indexing rules.

Complexity

For a balanced rope with n total characters:

Operation Best Average Worst Reason
Concatenate O(log n) O(log n) O(log n) Creates or adjusts logarithmic tree nodes
Split O(log n) O(log n) O(log n) Locates the boundary and separates tree paths
Character lookup O(log n) O(log n) O(log n) Descends through the chunk tree
Read k characters O(log n + k) O(log n + k) O(log n + k) Tree traversal plus output traversal
Build from a flat string O(n) O(n) O(n) Every character must be inspected and stored
Traverse or flatten O(n) O(n) O(n) Every character is visited

These bounds assume the rope remains balanced. An incorrectly balanced implementation can degrade toward O(n) for operations that should be logarithmic. Space usage is typically O(n) for the rope’s nodes and chunk contents. Structural sharing can reduce newly allocated space for a derived rope to approximately O(log n) nodes, but the original chunks remain retained as long as they are referenced. Auxiliary space is O(log n) for traversal stacks in typical implementations; the input rope itself is not counted as auxiliary space.

Common Pitfalls and Interview Tips

  • Do not claim that rope character lookup is O(1); that advantage belongs to flat, contiguous string representations.

  • Distinguish a rope operation that changes the tree from one that materializes a flat copy. Flattening the entire rope costs O(n).

  • Mention the assumptions behind logarithmic complexity: the tree must be balanced and operations must use structural sharing appropriately.

  • Explain that ropes are most beneficial for large, repeatedly edited strings, while normal str values are usually preferable for small or read-mostly text.

  • Edge cases include an empty rope, a rope containing one chunk, edits at chunk boundaries, and Unicode text whose chunk boundaries must not split invalidly. A rope library should handle these cases consistently.

13

Where are rope data structures used in practical applications?

A rope is a tree-based representation of a character sequence that supports efficient concatenation, splitting, insertion, and deletion without repeatedly copying the entire string. It is useful when applications manipulate large documents or other long text buffers frequently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Ropes Work

A rope divides text into smaller string chunks, called leaves, and connects them through internal nodes. Internal nodes represent the concatenation of their children, often storing the total character length.

For example:

  1. "abc" and "def" are stored as separate leaves.

  2. Their parent represents "abcdef" without copying either leaf into one contiguous buffer.

  3. Splitting at position 4 locates the boundary and creates subtrees representing "abcd" and "ef".

This structure is especially effective for large text because operations can share unchanged chunks instead of copying them.

Typical Complexities

The following assumes a balanced, eagerly rebalanced rope with cached subtree lengths. Under this implementation, the best-, average-, and worst-case time bounds have the same asymptotic forms.

Operation Time Space
Character lookup by index O(log n) O(1) auxiliary
Concatenation with rebalancing O(log n) O(log n) auxiliary
Split O(log n + k) O(log n + k), including new nodes and copied characters
Insertion or deletion O(log n + k) O(log n + k), including new nodes and copied characters
Substring extraction O(log n + k) O(log n + k), including copied output and path or stack space
Full flattening O(n) O(n) output plus O(log n) recursion stack
Full traversal O(n) O(log n) recursion stack

Here, n is the total number of characters and k is the number of characters copied or materialized. Auxiliary space excludes the existing input rope; copied output and newly allocated nodes are included where indicated. A fully materialized rope or contiguous string requires O(n) total space, including character data.

A lazy concatenation wrapper can make the immediate join O(1) in time and auxiliary space, but it defers balancing. Its eventual rebalancing cost depends on the implementation and accumulated imbalance, so it does not provide the same immediate concatenation bound as the eagerly rebalanced case.

Practical Applications

  • Text editors: Large documents can be edited without copying the entire file for every insertion or deletion.

  • Code editors and IDEs: Source files, project files, and search results are often represented as large text buffers that benefit from chunked editing.

  • Document-processing systems: Word processors, publishers, and note-taking applications can use ropes to support long documents and structural operations efficiently.

  • Collaborative editing: Chunked representations make it easier to reuse unchanged portions of a document when applying edits or generating versions.

  • Log viewers and file browsers: Large log files can be split into chunks for selective loading, display, and searching.

  • Diff and patch tools: Chunk-level text representations can reduce copying when comparing or modifying similarly structured documents.

  • Version-control and archival systems: Tree-structured text can help represent snapshots while sharing unchanged content, although systems such as Git commonly use additional mechanisms such as delta encoding rather than relying on a single rope implementation.

Rope Versus a Flat String

Property Rope Flat immutable string
Concatenation Efficiently shares existing chunks May copy the entire sequence
Insertion and deletion Avoids copying unaffected text Often requires rebuilding the sequence
Character lookup Usually O(log n) Usually O(1)
Contiguous access Requires flattening Directly available
Memory overhead Higher for nodes and metadata Lower for one flat buffer
Best fit Large, frequently edited text Small strings and simple read-only access

In Python 3.12, ordinary strings are immutable. Repeatedly using text += chunk in a loop can therefore become quadratic in the general case; the usual alternative is to collect chunks in a list and call "".join(chunks). A rope is a more advanced solution when the application needs both efficient editing and large text.

Common Pitfalls and Interview Tips

  • Do not assume every operation is cheap: lookup and editing may be logarithmic, but flattening the entire rope into one string costs O(n).

  • Clarify Unicode semantics: Python len counts Unicode code points, while byte-oriented systems count bytes. The rope must preserve the intended character model.

  • Mention balancing: Complexity guarantees depend on a balanced structure and cached subtree lengths; an unbalanced or poorly implemented tree can degrade toward linear behavior.

  • Protect shared data: Treat shared leaves as immutable or use copy-on-write, otherwise an edit could affect another branch or version.

  • Check boundary positions: split and substring positions are commonly zero-based and must be validated against the rope length.

  • Common follow-up questions: Compare ropes with str, explain substring extraction, discuss thread safety, and identify when a simple list of chunks is sufficient.

14

How do Ropes compare with StringBuilders?

A rope is a tree-like data structure optimized for efficient concatenation, insertion, deletion, and substring operations, while a StringBuilder is a mutable linear buffer optimized for appending characters and producing a final string. Ropes trade additional structural overhead for better large-scale editing, whereas StringBuilders are usually simpler and faster for sequential construction.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

  • Rope: Represents text as a balanced tree of character chunks or leaves. Operations can avoid copying unaffected portions of the text, and persistent implementations can share unchanged chunks between versions.

  • StringBuilder: Stores characters in a contiguous, growable buffer. It supports efficient appending and can be converted to an immutable string once construction is complete.

  • Typical StringBuilder implementation: Java’s StringBuilder and .NET’s StringBuilder are mutable and are not intended for concurrent mutation without external synchronization.

  • Python consideration: Python strings are immutable and there is no built-in StringBuilder equivalent. For repeated construction, collect pieces in a list and use ''.join(parts).

Complexity Comparison

The table assumes n total characters involved, m characters added, and k characters copied into a result. Rope bounds assume a balanced persistent tree with O(log n) height and bounded-size leaf chunks. Unless otherwise stated, best, average, and worst cases have the same bound under these assumptions.

Operation StringBuilder Rope
Append one constant-size unit Best O(1), average O(1) amortized, worst O(n) during buffer growth O(log n) to update the tree
Append an m-character chunk Best O(m), average O(m) amortized, worst O(n + m) O(m + log n) to copy the chunk and update the tree
Concatenate two texts O(n) because the characters are copied into a contiguous result O(log n) to join or rebalance tree pieces
Random character access O(1) O(log n)
Insert m characters in the middle O(n) because existing characters are shifted O(log n + m)
Delete a range O(n) because remaining characters are shifted O(log n) when deleted content is not copied
Create a substring O(k) because the result is copied O(log n) for a view; O(log n + k) when materialized
Flatten to one string O(n) O(n) to traverse and copy the leaves

StringBuilder appends are amortized O(1) for constant-size units: occasional buffer growth copies the buffer, but that cost is spread across many appends. Copying a longer chunk still costs at least O(m).

Space and Memory Behavior

  • StringBuilder: Uses O(n) buffer capacity, excluding the immutable final result, which may require another O(n) space.

  • Rope: Uses O(n) character storage plus O(r) metadata, where r is the number of tree nodes; r is O(n) in the worst case when leaves contain only a few characters.

  • Persistent edits: A small persistent edit typically adds O(log n) tree nodes plus the inserted characters because unchanged subtrees are shared.

  • Input counting: The original input text is excluded from additional-space figures. Materializing the final contiguous string adds O(n) output space.

  • Cache locality: A StringBuilder’s contiguous buffer generally has better cache locality than a rope’s tree of chunks.

When to Use Each

Use a StringBuilder when:

  • Characters or pieces are added mostly from left to right.

  • The final text is produced once and then read frequently.

  • Random access or tight memory overhead matters.

  • The algorithm does not perform repeated middle insertions or deletions.

Use a rope when:

  • Text is assembled from many large pieces.

  • Substrings, insertions, deletions, or concatenation occur repeatedly.

  • A persistent implementation can share unchanged text rather than copying it.

  • The text is eventually flattened or traversed as a whole.

For example, building a report from many independent sections may benefit from a rope if sections are repeatedly rearranged. Building the same report once from small append operations is usually simpler and faster with a StringBuilder.

Common Pitfalls

  • Assuming every rope has O(1) concatenation: The bound depends on tree height, balancing, and implementation.

  • Ignoring copied chunk lengths: Appending m characters costs at least O(m) even when the structure provides amortized constant-time appends for single units.

  • Ignoring flattening cost: A rope can delay copying, but producing the final contiguous string still takes O(n).

  • Choosing a rope for simple append-only work: Tree overhead may outweigh the benefits when edits are rare.

  • Confusing characters and bytes: Complexities usually count characters or bytes consistently; UTF-8 storage size may differ from the number of Unicode code points.

  • Mutating input unexpectedly: StringBuilder operations modify the builder. If multiple versions are needed, copy or preserve the original text deliberately.

  • Forgetting thread safety: A mutable StringBuilder is generally not safe for unsynchronized concurrent modification.

15

How do Strings and Ropes differ in performance?

Strings are typically flat, immutable sequences, whereas ropes represent text as a balanced tree of chunks. Strings provide fast indexed access, while ropes make repeated structural operations such as concatenation, insertion, and splitting much more efficient.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Representation

A conventional string stores its native units in one contiguous allocation. It is simple and cache-friendly, but modifying it creates a new value.

A rope represents text hierarchically:

  • Leaves contain chunks of text.

  • Internal nodes combine or describe child chunks.

  • Metadata such as subtree length and sometimes cached hashes is stored at nodes.

  • Persistent implementations can share unchanged subtrees between versions.

Ropes are not a standard Python feature. Some text editors and JavaScript engines use similar tree-based techniques internally.

Performance Comparison

Let n and m be the input lengths and k the substring length. The bounds below assume a height-balanced rope. Unless noted, the time bounds are the same in the best, average, and worst cases.

Operation Flat immutable string Balanced rope
Read one indexed unit Θ(1) time, Θ(1) auxiliary space Θ(log n) time, Θ(1) auxiliary space
Get length Θ(1) time and space Θ(1) time and space when lengths are cached
Concatenate Θ(n + m) time and Θ(n + m) new output space Θ(log(n + m)) time and new-node space
Create substring Θ(k) time and Θ(k) output space for a copying API Θ(log n) time and space for a lazy view; Θ(log n + k) to materialize
Insert or remove Θ(n) time and new output space Θ(log n) time and new-node space
Traverse all units Θ(n) time, Θ(1) auxiliary space Θ(n) time, Θ(log n) traversal-stack space with depth-first traversal
Flatten Already flat Θ(n) time, Θ(n) output space, plus Θ(log n) traversal stack

Comparing two sequences takes up to Θ(n) time in the worst case without memoized subtree comparisons; unequal lengths or an early mismatch can finish in Θ(1). Equality can be O(1) in the best case when both references identify the same object, and a rope can shortcut identical shared subtrees.

Computing an uncached content hash takes Θ(n) time. A rope can cache hashes at nodes, making subsequent root-hash retrieval O(1); caching a hash at every node requires Θ(n) additional storage.

These space bounds count newly created output and auxiliary storage but not the original input unless it is replaced.

When Ropes Perform Better

Ropes are useful for large documents that are repeatedly edited or combined:

  • Concatenation creates a small tree of nodes instead of copying all characters.

  • Insertion and deletion update only a path through the tree.

  • Splitting can create views that share existing chunks.

  • Persistent versions can share almost all their storage, supporting undo, history, and collaborative editing.

These logarithmic bounds require balanced trees. An unbalanced rope can degrade toward linear-time access or editing.

Python 3.12 Behavior

Python’s str is immutable and represents a sequence of Unicode code points. Compact internal representations allow one, two, or four bytes per code point depending on the characters, but len counts code points rather than bytes or grapheme clusters.

Python slicing creates a copy, so text[start:end] takes Θ(k) time and output space. Repeated immutable concatenation can take Θ(n²) total time in implementations that copy the growing result on every update; CPython can optimize some local += patterns, but applications should not depend on that optimization.

For predictable linear behavior, collect fragments in a list and join them once. Joining fragments with total length L takes Θ(L) time and Θ(L) output space. Python provides no built-in rope.

Advantages and Trade-offs

  • Strings: constant-time indexed access, simple APIs, good cache locality, and straightforward comparison and hashing.

  • Ropes: efficient concatenation, splitting, persistent editing, and structural sharing, at the cost of slower random access and greater implementation complexity.

Use ordinary strings for typical application text with infrequent edits. Ropes are advantageous for large, frequently edited, or versioned documents.

Common Pitfalls

  • Do not assume rope indexing is constant time.

  • Do not treat rope concatenation as allocation-free; creating balanced nodes still costs Θ(log n) time and space.

  • Include materialized output and recursion or traversal-stack space in complexity claims.

  • Distinguish bytes, Unicode code points, and user-perceived grapheme clusters.

  • Do not assume Python provides a built-in rope.

  • A common follow-up asks why repeated immutable concatenation can become Θ(n²): each update may copy the growing result, whereas a rope shares existing chunks.

16

How does Boyer-Moore string search work?

Boyer–Moore is a string-search algorithm that compares characters from right to left and skips alignments that cannot produce a match. The complete algorithm combines a bad-character rule with a good-suffix rule to achieve linear worst-case search time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Given text and pattern, the algorithm keeps a possible starting position in the text called an alignment.

  1. Compare the pattern’s last character with the corresponding text character.

  2. Continue comparing leftward while the characters match.

  3. On a mismatch, use the bad character to calculate a safe positive shift.

  4. Move the alignment by that amount and repeat.

  5. Return the alignment when every pattern character matches.

For the bad-character rule, let the mismatch occur at pattern index j and the unmatched text character be c:

  • If c previously appeared at pattern index i < j, shift by j - i. This aligns the earlier c with the unmatched text character.

  • Otherwise, shift by j + 1.

The full Boyer–Moore algorithm adds a good-suffix rule. When a suffix of the pattern has already matched, it uses the pattern’s borders or overlaps to shift without unnecessarily repeating comparisons.

Example Walkthrough

For text = "ABABC" and pattern = "ABC":

Alignment Right-to-left comparison Action
0 C versus B Mismatch at pattern index 2; shift by 1
1 C versus B Mismatch at pattern index 2; shift by 1
2 C = C, B = B, A = A Match found at index 2

Code Example

This implementation demonstrates the core bad-character-only Boyer–Moore variant. It returns the first match or -1 if none exists.

from bisect import bisect_left
from collections import defaultdict


def boyer_moore_search(text: str, pattern: str) -> int:
    """Return the first index of pattern in text, or -1 if absent."""
    text_length = len(text)
    pattern_length = len(pattern)

    if pattern_length == 0:
        return 0
    if pattern_length > text_length:
        return -1

    occurrences: defaultdict[str, list[int]] = defaultdict(list)
    for index, character in enumerate(pattern):
        occurrences[character].append(index)

    alignment = 0

    while alignment <= text_length - pattern_length:
        mismatch_index = pattern_length - 1

        # Compare from right to left.
        while (
            mismatch_index >= 0
            and text[alignment + mismatch_index] == pattern[mismatch_index]
        ):
            mismatch_index -= 1

        if mismatch_index < 0:
            return alignment

        bad_character = text[alignment + mismatch_index]
        positions = occurrences.get(bad_character, [])

        # Find the closest occurrence strictly before mismatch_index.
        insertion_point = bisect_left(positions, mismatch_index)
        if insertion_point > 0:
            previous_position = positions[insertion_point - 1]
            shift = mismatch_index - previous_position
        else:
            shift = mismatch_index + 1

        alignment += shift

    return -1


print(boyer_moore_search("ABABC", "ABC"))  # 2

Complexity

Let n be the text length, m the pattern length, and σ the alphabet size.

Approach Best Average Worst Auxiliary Space
Bad-character-only code O(m) O(n) on typical inputs O(nm) O(m)
Full Boyer–Moore O(m) O(n) overall O(n+m) O(m + σ)
  • Best case, O(m): all pattern characters match at the first alignment.

  • Bad-character worst case, O(nm): alignments may advance by one while many characters are compared.

  • Full worst case, O(n + m): adding the good-suffix rule prevents repeated quadratic work.

  • The code stores one occurrence-list entry per pattern position, so it uses O(m) auxiliary space, excluding the input strings.

  • The implementation is iterative and uses no recursion stack.

  • Preprocessing takes O(m) expected time because it uses a hash-based dictionary.

Edge Cases

  • Empty pattern: the function returns 0, following the common convention that it matches at the beginning.

  • Empty text: a nonempty pattern returns -1.

  • Single-character input: a matching one-character pattern returns 0; otherwise, the result is -1.

  • Pattern longer than text: returns -1 immediately.

  • Duplicate characters: handled through sorted occurrence lists.

  • Unicode: Python str characters are Unicode code points; len counts code points, not encoded bytes.

  • No match: the alignment eventually moves beyond the final valid starting position.

Common Pitfalls

  • Comparing left to right eliminates most of Boyer–Moore’s skipping advantage.

  • Confusing the previous occurrence with the next occurrence produces invalid shifts.

  • Claiming that the bad-character-only implementation has O(n) worst-case time; only the full algorithm with the good-suffix rule has a linear worst-case guarantee.

  • Forgetting the empty-pattern and pattern-longer-than-text cases.

  • Interviewers commonly follow up by asking how the good-suffix rule works, why the shifts are safe, and how Boyer–Moore compares with KMP.

17

How do Knuth-Morris-Pratt, Boyer-Moore, and Rabin-Karp string search compare?

Knuth-Morris-Pratt (KMP) guarantees linear-time matching, Boyer-Moore can be very fast in practice because it skips positions, and Rabin-Karp compares rolling hashes. Their trade-offs involve preprocessing, worst-case behavior, probabilistic guarantees, and use of extra space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Ideas

  • KMP: Preprocesses the pattern into a prefix-function table. On a mismatch, it uses that table to determine how much of the already matched prefix can be reused without moving backward.

  • Boyer-Moore: Aligns the pattern with the text and compares characters from the pattern’s end. A mismatch allows it to skip several text positions using bad-character and good-suffix rules.

  • Rabin-Karp: Assigns numeric hashes to the pattern and each text window. A rolling hash updates the current window’s hash in constant time, so most comparisons require only hash-equality checks.

  • Naive search: Restarts after every mismatch. It is simple but can repeatedly compare the same characters.

Complexity Comparison

Let n be the text length, m the pattern length, and Σ the alphabet size. Extra space excludes the input strings; standard iterative implementations use constant recursion-stack space.

Algorithm Preprocessing Best Time Average Time Worst Time Extra Space
Naive O(1) O(m) O(nm) O(nm) O(1)
KMP O(m) O(n+m) O(n+m) O(n+m) O(m)
Boyer-Moore O(m + Σ ) O(n) Typically O(m + n/m) O(nm) O(m + Σ )
Rabin-Karp O(m) O(n+m) Expected O(n+m) O(nm) O(1) with a rolling hash
  • KMP is deterministically linear because the text pointer never moves backward.

  • Boyer-Moore commonly performs around O(n/m) character comparisons, although preprocessing costs O(m). Its bad-character and good-suffix shifts do not guarantee linear worst-case time without an additional rule such as Galil’s rule.

  • Rabin-Karp is expected linear when suitable randomized hashing makes collisions sufficiently rare. With a fixed hash, linear time is not guaranteed; if every window collides and every candidate is verified character by character, its worst case becomes O(nm).

  • Hash arithmetic is conventionally treated as constant time. Very large arbitrary-precision integers can introduce bit-complexity considerations.

When to Use Each Algorithm

  • KMP: Choose it when deterministic worst-case linear time is important or when the pattern is searched repeatedly in long texts.

  • Boyer-Moore: Choose it for typical single-pattern searches where practical speed matters more than a deterministic linear-time guarantee.

  • Rabin-Karp: Choose it for exact matching when a rolling-hash implementation and expected linear behavior are suitable. For many static patterns, Aho-Corasick is usually preferable, although a set of pattern hashes can support a smaller multiple-pattern workload.

  • Naive search: Use it only for very short patterns, small inputs, or educational purposes.

  • Approximate matching: Use a specialized fuzzy-matching algorithm or an explicitly modified Rabin-Karp variant; ordinary Rabin-Karp only detects exact matches.

Small KMP Walkthrough

For pattern ABAB, the prefix function is:

Index Character Prefix-function value
0 A 0
1 B 0
2 A 1
3 B 2

When scanning ABABABC:

  1. A matches, so the matched-prefix length becomes 1.

  2. B matches, making it 2.

  3. A matches, making it 3.

  4. B matches, making it 4; the complete pattern is found at index 3.

The prefix table allows KMP to recover efficiently after later mismatches.

Common Pitfalls

  • Empty pattern: Define its behavior explicitly—many implementations return 0 immediately.

  • Pattern longer than text: Return no match without attempting unnecessary comparisons.

  • Off-by-one errors: Carefully track whether match positions are zero-based or one-based.

  • Hash collisions: Rabin-Karp should verify hash matches before accepting them; otherwise it can report false positives.

  • Unicode versus bytes: Python’s len counts Unicode code points, while encoded byte searches operate on bytes. State the representation being searched.

  • Case sensitivity: Normalize the strings or specify a case-insensitive comparison policy before searching.

  • Preprocessing cost: For repeated searches of the same pattern, KMP or Boyer-Moore preprocessing is amortized by reusing the pattern tables.

18

How do you implement pattern searching with the Z-algorithm?

The Z-algorithm finds every occurrence of a pattern in linear time by computing how many characters match at each position. For pattern searching, the pattern and text are combined with a unique separator, and matching Z-values identify the pattern’s starting positions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a sequence s, the Z-array stores z[i], the length of the longest common prefix between s and the suffix beginning at i.

For example, given s = "ABABAB":

  • z[0] = 0 by convention.

  • z[2] = 4 because "ABAB" matches the first four characters.

  • z[1] = 0 because the suffix "BABAB" starts with a different character.

To search for a pattern, the implementation constructs:

pattern + unique_separator + text

If the pattern has length m, a Z-value of m at a position in the text means a complete match occurs there. Python’s None is used as the separator because it cannot equal any character in a str.

The algorithm maintains a matching interval [left, right). When a position lies inside that interval, its previously calculated Z-value provides an initial comparison length, avoiding repeated character comparisons.

Complexity

Let n be the text length and m the pattern length.

Approach Best time Average time Worst time Auxiliary space When to use
Brute-force comparison O(n) O(n) for random inputs O(nm) O(1) Very short patterns or simple implementations
Z-algorithm O(n + m) O(n + m) O(n + m) O(n + m) Guaranteed linear-time pattern searching
  • Time: O(n + m) in all cases for the Z-algorithm. The right boundary advances at most n + m times, while failed comparisons add only linear overhead.

  • Space: O(n + m) auxiliary space for the combined sequence and Z-array, excluding the returned matches. The input itself is not counted, although the algorithm internally copies its characters into a combined sequence.

  • Recursion stack: None; the implementation is iterative.

  • Output space: O(k), where k is the number of matches. Since k ≤ n + 1, total additional space remains O(n + m).

  • Empty pattern: Returns all n + 1 boundary positions in O(n) time, using the convention that an empty pattern matches at every boundary.

  • Pattern longer than the text: Returns an empty list in O(1) time.

Example Walkthrough

For text = "ABABAB" and pattern = "ABAB", the combined sequence is conceptually:

ABAB#ABABAB

The text starts at index 5.

Text start Text suffix Matching prefix length Match
0 ABABAB 4 Yes
1 BABAB 0 No
2 ABAB 4 Yes
3 BAB 0 No
4 AB 0 No

The returned starting indices are [0, 2].

Code Example

from collections.abc import Sequence


def _z_array(sequence: Sequence[object]) -> list[int]:
    """Return the Z-value for every position in the sequence."""
    length = len(sequence)
    z_values = [0] * length
    left = right = 0  # Current matching interval is [left, right)

    for index in range(1, length):
        if index < right:
            mirrored_index = index - left
            z_values[index] = min(
                right - index,
                z_values[mirrored_index],
            )

        while (
            index + z_values[index] < length
            and sequence[z_values[index]]
            == sequence[index + z_values[index]]
        ):
            z_values[index] += 1

        if index + z_values[index] > right:
            left = index
            right = index + z_values[index]

    return z_values


def z_pattern_search(text: str, pattern: str) -> list[int]:
    """Return every starting index where pattern occurs in text."""
    if not pattern:
        return list(range(len(text) + 1))

    if len(pattern) > len(text):
        return []

    # None is a separator that cannot occur inside a Python string.
    sequence: list[object] = [*pattern, None, *text]
    z_values = _z_array(sequence)

    text_start = len(pattern) + 1
    pattern_length = len(pattern)

    return [
        index - text_start
        for index in range(text_start, len(sequence))
        if z_values[index] == pattern_length
    ]


print(z_pattern_search("ABABAB", "ABAB"))  # [0, 2]

Common Pitfalls

  • Off-by-one errors: Treat right as an exclusive boundary and subtract the text offset from each global match position.

  • Separator collisions: A textual separator can occur inside the input. None avoids this problem entirely.

  • Overlapping matches: Do not advance past a match by the pattern length. The implementation correctly reports overlapping occurrences.

  • Unicode assumptions: Python str indexing operates on Unicode code points, so len counts code points rather than encoded bytes.

  • Unnecessary input mutation: The algorithm does not modify either string.

  • Common follow-up questions: Interviewers may ask how Z-algorithm differs from KMP, how to search for multiple patterns, or how the algorithm would be adapted to a streaming input.

19

How does the BNDM algorithm work for string matching?

BNDM (Backward Nondeterministic DAWG Matching, Navarro and Raffinot) finds a pattern of length m by reading each text window from right to left and tracking, in one bit mask, every position where the characters read so far appear as a substring of the pattern. When that set becomes empty it skips ahead, often by almost m characters, so on typical text it reads only a fraction of the input. It combines Boyer-Moore-style backward scanning with bit-parallel simulation of a suffix automaton, and is fast for short patterns that fit in a machine word.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Preprocessing

For each character c, build a mask B[c] with bit m - 1 - i set when pattern[i] == c. Pattern "abab" gives:

Character Positions in pattern B[c]
a 0, 2 1010
b 1, 3 0101
anything else none 0000

This costs O(m + σ) time and O(σ) space, where σ is the alphabet size (only characters in the pattern need entries if you use a dictionary).

Searching a Window

For the window starting at pos:

  1. Set state to all ones (every pattern position is still possible) and j = m.

  2. Read text[pos + j - 1], the next character from the right, and set state &= B[c].

  3. Decrement j. If the top bit of state is set, the characters read so far are a prefix of the pattern. If j > 0, remember last = j, the safe shift. If j == 0, the whole window equals the pattern: report a match.

  4. Shift state left by one (masked to m bits) and repeat while state is non-zero.

  5. Move the window by last. The shift is safe because any earlier start would need a pattern prefix that the scan did not see.

Code Example

def bndm_search(text: str, pattern: str) -> list[int]:
    """Return every start index of pattern in text using BNDM."""
    m = len(pattern)
    n = len(text)
    if m == 0:
        return list(range(n + 1))

    masks: dict[str, int] = {}
    for i, character in enumerate(pattern):
        masks[character] = masks.get(character, 0) | (1 << (m - 1 - i))

    full = (1 << m) - 1
    high_bit = 1 << (m - 1)
    matches: list[int] = []
    pos = 0

    while pos <= n - m:
        j = m
        last = m
        state = full
        while state:
            state &= masks.get(text[pos + j - 1], 0)
            j -= 1
            if state & high_bit:
                if j > 0:
                    last = j
                else:
                    matches.append(pos)
                    break
            state = (state << 1) & full
        pos += last
    return matches


print(bndm_search("abcabab", "abab"))  # [3]
print(bndm_search("aaaa", "aa"))       # [0, 1, 2]

Walkthrough

Text "abcabab", pattern "abab" (m = 4):

Window pos j after read Character state Note
0 3 a 1010 top bit set: a is a prefix, last = 3
0 2 c 0000 c is not in the pattern, stop
shift by 3
3 3 b 0101
3 2 a 1010 prefix ab seen, last = 2
3 1 b 0100
3 0 a 1000 j == 0 with top bit: match at 3

Complexity

Algorithm Preprocessing Search best Search average Search worst Extra space
Naive none O(n) O(n) O(n·m) O(1)
KMP O(m) O(n) O(n) O(n) O(m)
Boyer-Moore-Horspool O(m + σ) O(n/m) about O(n/m) O(n·m) O(σ)
BNDM O(m + σ) O(n/m) O(n·log_σ(m) / m) O(n·m) O(σ)

These figures assume m is at most the word size w (64), so each mask operation is O(1). For longer patterns each operation costs O(m/w); Python’s unbounded integers hide this but do not remove it. The output list is O(occ) extra. The best case occurs when the last character of each window is absent from the pattern, so each window costs one read and shifts by m. The worst case, such as text "aaaa…" and pattern "aa…a", reads every window fully. The search is iterative, so there is no recursion stack.

Interview Tips

  • Explain the meaning of state: bit k set means “the characters read so far from the right occur in the pattern at one specific position”. That one sentence shows you understand the bit-parallel trick.

  • Compare with Shift-Or, which scans forward with the same kind of masks but never skips characters.

  • Mention when not to use it: patterns much longer than a machine word lose the bit-parallel advantage, and for everyday code the library’s str.find (a tuned Horspool-style search that switches to the two-way algorithm for long patterns) is the better choice.

  • Pitfalls to avoid: forgetting to mask the shift to m bits, using the wrong bit order in B[c], and forgetting overlapping matches ("aa" in "aaaa" has three).

20

How to check balanced parentheses in linear time and constant space?

A string has balanced parentheses when every closing parenthesis ) has a preceding unmatched opening parenthesis (, and no opening parentheses remain unmatched. For strings containing only these two characters, a single counter is sufficient, giving O(n) time and O(1) auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Maintain an open_count counter:

  • Opening parenthesis (: increment open_count.

  • Closing parenthesis ): decrement open_count.

  • If open_count becomes negative, return False immediately because a closing parenthesis appeared without a matching opening one.

  • After scanning the string, return open_count == 0.

The implementation ignores non-parenthesis characters and checks only the parentheses they contain.

Example Walkthrough

For the string "(()":

Step Character open_count Result
1 ( 1 Continue
2 ( 2 Continue
3 ) 1 Continue

The final count is 1, so the string is not balanced.

Complexity

Let n be the number of characters in the input.

Case Time Reason
Best O(n) The scan still examines every character in the worst-case input shape
Average O(n) Each character is processed once
Worst O(n) Each character is processed once
  • Auxiliary space: O(1), because only one integer counter is used.

  • The input string is not copied or modified, so the input itself is not counted as auxiliary space.

  • There is no recursion stack.

Code Example

def is_balanced_parentheses(text: str) -> bool:
    """Check whether the parentheses in text are balanced."""
    open_count = 0

    for character in text:
        if character == "(":
            open_count += 1
        elif character == ")":
            open_count -= 1
            if open_count < 0:
                return False

    return open_count == 0


print(is_balanced_parentheses("(()())"))  # True

Common Pitfalls

  • Checking only at the end: "())" has a final count of 0, but it is invalid because the second ) appears too early. The negative-count check must happen during the scan.

  • Empty input: By the standard convention, an empty string is balanced, so the function returns True.

  • Single parentheses: Both "(" and ")" are unbalanced.

  • Multiple bracket types: A counter works for only ( and ). Mixed types such as (), [], and {} require a stack, which uses O(n) space in the worst case.

  • Unexpected characters: This implementation ignores them. If only ( and ) are valid input, validate that requirement separately.

21

How do you remove the fewest parentheses to balance a string?

Minimum-parentheses removal produces a valid balanced string by deleting the minimum number of parentheses while preserving the order of all remaining characters. The greedy approach removes unmatched closing parentheses from left to right, then unmatched opening parentheses from right to left.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A parentheses string is valid when:

  • The number of ( equals the number of ).

  • In every prefix, the number of ( is at least the number of ).

Use two directional scans:

  1. Scan from left to right, matching each ) with an available earlier (.

  2. If a ) has no available (, mark it for removal.

  3. Scan the remaining characters from right to left, matching each ( with an available later ).

  4. If an ( has no available ), mark it for removal.

This greedy matching maximizes the number of matched pairs, so the number of deleted parentheses is minimal.

Let n be the input length and p the number of parentheses:

Approach Time Space When to use
Brute force: try every subset of parentheses O(n · 2^p) O(n) working space Tiny inputs or generating candidates one at a time
Greedy two-pass matching O(n) O(n) auxiliary space Producing one minimum-removal result efficiently

The brute-force working-space figure excludes the input and any candidates retained by the caller.

Example Walkthrough

For ())(():

Step Action Result
1 Scan left to right The first ) matches the first (
2 The next ) has no available ( Mark it for removal
3 Scan the remaining string from right to left The final ) matches the preceding (
4 The remaining earlier ( has no available closing parenthesis remaining to its right Mark it for removal
5 Join the unmarked characters ()()

Two parentheses were removed, which is minimal.

Complexity

Let n be the length of the input string.

Case Time Space
Best O(n) O(n) auxiliary
Average O(n) O(n) auxiliary
Worst O(n) O(n) auxiliary

The algorithm performs two linear scans and one final join. Auxiliary space is O(n) because it stores removal flags and constructs the result; the input string itself is not counted. Including the returned string, total space remains O(n). There is no recursion stack.

Code Example

def remove_min_parentheses(text: str) -> tuple[str, int]:
    """Remove the fewest parentheses needed to make the parentheses balanced."""
    remove = [False] * len(text)

    # Match closing parentheses with opening parentheses to their left.
    available_opens = 0
    for index, character in enumerate(text):
        if character == "(":
            available_opens += 1
        elif character == ")":
            if available_opens == 0:
                remove[index] = True
            else:
                available_opens -= 1

    # Match opening parentheses with closing parentheses to their right.
    available_closes = 0
    for index in range(len(text) - 1, -1, -1):
        if remove[index]:
            continue

        character = text[index]
        if character == ")":
            available_closes += 1
        elif character == "(":
            if available_closes == 0:
                remove[index] = True
            else:
                available_closes -= 1

    result = "".join(
        character
        for index, character in enumerate(text)
        if not remove[index]
    )
    return result, sum(remove)


balanced, removed = remove_min_parentheses("())(()")
print(balanced)  # Expected: ()()
print(removed)   # Expected: 2

The function preserves non-parenthesis characters and uses ''.join(...) rather than repeatedly concatenating strings with +=, which could become quadratic.

Common Pitfalls

  • Empty input: Returns ("", 0).

  • One element: Removes the unmatched parenthesis, if applicable.

  • Only opening parentheses: Removes all of them.

  • Only closing parentheses: Removes all of them.

  • Already balanced input: Returns the original string with 0 removals.

  • Duplicate or repeated parentheses: Handles them through the same matching process.

  • Negative or unrelated characters: Treats them as ordinary characters; only parentheses affect validity.

  • Unicode: Python indexes and len() count Unicode code points, while only the ASCII characters ( and ) are treated as parentheses.

  • Common mistake: Removing parentheses without preserving their original order can produce a different result; always retain the unmarked characters in sequence.

  • Common follow-up: Ask how to return all distinct valid strings, which typically requires backtracking rather than this greedy solution.

22

How do you reverse a string using a stack?

A stack reverses a string by pushing each character onto the stack and then popping characters in last-in, first-out (LIFO) order. Because each popped character is the last one pushed, the resulting sequence is the reverse of the original string.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Create an empty stack.

  2. Push characters from left to right into the stack.

  3. Pop characters from the stack one at a time.

  4. Join the popped characters into a new string.

For "hello":

Operation Stack after operation Output so far
Push h h —
Push e h, e —
Push l h, e, l —
Push l h, e, l, l —
Push o h, e, l, l, o —
Pop o h, e, l, l o
Pop l h, e, l ol
Pop l h, e oll
Pop e h olle
Pop h empty olleh

In Python, strings are immutable, so the implementation uses a list as the stack and joins the popped characters at the end. Python string indexing and len() count Unicode code points, so this reverses code points rather than user-perceived grapheme clusters such as an emoji with multiple code points.

Complexity

Let n be the number of characters in the input string.

  • Time: O(n) — every character is pushed once and popped once.

  • Space: O(n) — the stack and the output list each store up to n characters. The input string is not counted as additional space.

Code Example

class CharacterStack:
    """A LIFO stack for storing individual characters."""

    def __init__(self) -> None:
        self._items: list[str] = []

    def push(self, character: str) -> None:
        """Add a character to the top of the stack."""
        self._items.append(character)

    def pop(self) -> str:
        """Remove and return the top character."""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def is_empty(self) -> bool:
        """Return whether the stack contains no characters."""
        return not self._items


def reverse_string(text: str) -> str:
    """Return the characters of text in reverse order using a stack."""
    stack = CharacterStack()

    for character in text:
        stack.push(character)

    reversed_characters: list[str] = []
    while not stack.is_empty():
        reversed_characters.append(stack.pop())

    return "".join(reversed_characters)


print(reverse_string("hello"))  # olleh

Common Pitfalls

  • Using += in a loop: Repeatedly appending to an immutable Python string can lead to O(n²) behavior. Use a list and ''.join(...) instead.

  • Using pop(0): Removing the first element from a list is O(n) because the remaining elements must shift. Pop from the end instead.

  • Assuming bytes and characters are identical: In Python, bytes stores byte values, while str stores Unicode code points. The code above reverses str characters.

  • Forgetting empty input: The implementation handles "" by returning an empty string. One-character strings, duplicates, and whitespace are preserved in reversed order.

  • Unicode display concerns: Reversing code points may not always reverse a user-perceived grapheme cluster. Applications that require grapheme-aware reversal need a Unicode grapheme-segmentation library.

23

How do you solve the String Compression problem?

Run-length encoding compresses consecutive equal characters by replacing each run with the character followed by its count. For example, "aaabccddd" becomes "a3b1c2d3".

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Scan the string once while tracking:

  • run_char: The character currently being counted.

  • run_length: How many times it has appeared consecutively.

  • parts: Compressed fragments stored for a final join.

When the next character differs from run_char, append the completed run and start a new one. This compresses only consecutive repetitions, not every occurrence of a character across the entire string.

Complexity

Let n be the number of Unicode code points in the input.

Case Time Space
Best O(n) O(n)
Average O(n) O(n)
Worst O(n) O(n)
  • Time: Every character is visited once, and constructing the output is linear in its size.

  • Space: O(n) additional space for the fragment list and returned string. The input is not counted, and there is no recursion stack.

  • Empty input: Returns in O(1) time and uses O(1) space.

  • One-character input: Returns the character followed by 1, such as "a1".

  • Duplicates: Consecutive duplicates form one run, while nonconsecutive occurrences belong to separate runs.

Walkthrough

For "aaabccddd":

  1. Read three a characters and append "a3".

  2. Read one b character and append "b1".

  3. Read two c characters and append "c2".

  4. Read three d characters and append "d3".

  5. Join the fragments into "a3b1c2d3".

Code Example

def compress_string(text: str) -> str:
    """Compress consecutive character runs as character plus count."""
    if not text:
        return ""

    parts: list[str] = []
    run_char = text[0]
    run_length = 1

    for index in range(1, len(text)):
        char = text[index]

        if char == run_char:
            run_length += 1
        else:
            parts.append(f"{run_char}{run_length}")
            run_char = char
            run_length = 1

    # Include the final run.
    parts.append(f"{run_char}{run_length}")

    return "".join(parts)


print(compress_string("aaabccddd"))  # a3b1c2d3

Best Practices

  • Use join(): Build fragments in a list and join them once. Repeatedly using result += fragment in a loop can become O(n²).

  • Avoid unnecessary slicing: text[1:] creates an O(n) copy; indexed access keeps auxiliary usage predictable.

  • Preserve explicit counts: This format includes counts of 1, producing "b1" rather than simply "b".

  • Handle empty input explicitly: Returning "" avoids indexing text[0].

  • Consider Unicode: Python strings represent Unicode code points, so len(text) counts code points, not encoded bytes or user-perceived characters.

  • Check whether compression helps: Run-length encoding can make short or nonrepetitive strings longer; omit counts of 1 if the goal is to minimize output size.

Common Pitfalls

  • Off-by-one errors: The final run must be appended after the loop.

  • Quadratic string building: Appending to an immutable string in a loop may repeatedly copy the accumulated result.

  • Incorrect grouping: The algorithm compresses consecutive runs, not all occurrences of a character.

  • Mutating the input: Strings are immutable; a non-mutating implementation avoids unnecessary copies.

  • Ambiguous output: Formats such as "a1112" can be difficult to decode when original characters are digits. If decoding is required, define separators or another unambiguous encoding.

Interviewers may follow up by asking for a decoder, an “original length versus compressed length” comparison, or a variant that only emits a count when it saves space.

24

How do I find the longest palindromic substring in Python 3.12?

The longest palindromic substring is the longest contiguous sequence of characters that reads identically forward and backward. Manacher’s algorithm finds it in linear time by reusing previously computed palindrome radii instead of expanding independently around every possible center.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Manacher’s algorithm transforms the string so that odd- and even-length palindromes both have a single-character center:

  • text = "abba" becomes #a#b#b#a#.

  • radius[center] records the maximum palindrome radius around that position.

  • center and right track the palindrome whose right boundary currently reaches farthest.

  • If the current position is inside that palindrome, its mirrored position provides an initial radius.

  • Expansion continues only as needed to determine the exact radius.

The separator is represented by None, so it cannot accidentally match a character in the input.

Approach Time Auxiliary space When to use
Check every substring O(n³) O(1) Educational or very short strings
Expand around every center O(n²) O(1) Simple implementation with modest input sizes
Manacher’s algorithm O(n) O(n) Large inputs or interview optimization

Why It Works

Every palindrome has a center, whether its length is odd or even. The separator transformation represents both cases uniformly.

When a position lies inside the known palindrome, symmetry guarantees that its initial radius is at least the mirrored radius. If that radius reaches the known boundary, further expansion is required to find the exact maximum. Expanding from that point therefore computes the correct radius for every center.

The transformed radius of the largest palindrome equals the number of original characters in that palindrome, so the maximum radius identifies the answer.

Complexity

For a string of length n:

  • Best-case time: O(n). The transformed array, radius array, and initial setup require linear work.

  • Average-case time: O(n). Successful expansions extend the known boundary, which can happen only O(n) times overall.

  • Worst-case time: O(n). Repeated characters do not make the algorithm quadratic because mirrored information is reused.

  • Auxiliary space: O(n) for the transformed sequence and radius array, excluding the input and returned substring.

  • Output space: O(k), where k is the answer’s length.

  • Total space including input and output: O(n).

  • Recursion stack: O(1), because the implementation is iterative.

Code Example

def longest_palindromic_substring(text: str) -> str:
    """Return the longest contiguous palindromic substring of text."""
    if not text:
        return ""

    # Separators make odd- and even-length palindromes use one center model.
    transformed: list[str | None] = [None] * (2 * len(text) + 1)
    transformed[1::2] = text

    radii = [0] * len(transformed)
    center = 0
    right = 0
    best_center = 0
    best_radius = 0

    for position in range(len(transformed)):
        if position < right:
            mirror = 2 * center - position
            radii[position] = min(right - position, radii[mirror])

        # Expand beyond the mirrored or initially known radius.
        while (
            position - radii[position] - 1 >= 0
            and position + radii[position] + 1 < len(transformed)
            and transformed[position - radii[position] - 1]
            == transformed[position + radii[position] + 1]
        ):
            radii[position] += 1

        if position + radii[position] > right:
            center = position
            right = position + radii[position]

        if radii[position] > best_radius:
            best_center = position
            best_radius = radii[position]

    start = (best_center - best_radius) // 2
    return text[start:start + best_radius]


print(longest_palindromic_substring("abba"))  # "abba"

Walkthrough and Edge Cases

For "abba":

  1. The transformed sequence is #a#b#b#a#.

  2. At the separator between the two b characters, the radius expands through matching b, #, a, and # pairs.

  3. The maximum radius is 4, corresponding to four original characters.

  4. The start index is (4 - 4) // 2 = 0, so the result is "abba".

Relevant edge cases:

  • Empty input: Returns "".

  • One character: Returns that character.

  • Duplicate characters: Handled normally; for example, "aaaa" returns "aaaa".

  • Multiple answers: Returns the first maximum encountered because the implementation updates only for a strictly larger radius.

  • Unicode: Python str indexes Unicode code points, so palindrome comparisons use code points rather than bytes or user-perceived grapheme clusters.

  • Negative numbers, sorted input, disconnected graphs, and cycles are not applicable to this substring problem.

Common Pitfalls

  • Off-by-one errors: Carefully distinguish the transformed radius, original start index, and original substring length.

  • Character versus byte confusion: len(text) counts Unicode code points for str; bytes instead counts bytes.

  • Repeated concatenation: Avoid building large strings with += inside loops because Python strings are immutable. Use ''.join(parts) when multiple pieces must be combined.

  • Slicing cost: Python slicing creates a new string and costs O(k) time and space.

  • Unnecessary mutation: The algorithm does not modify the input.

  • Common follow-up: Distinguish a palindromic substring, which must be contiguous, from a palindromic subsequence, which may skip characters.

25

How to verify if a string reads the same forward and backward?

A palindrome reads the same forward and backward. Verify one by comparing characters at symmetric positions with two pointers, stopping immediately at the first mismatch.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Initialize pointers: Set left to 0 and right to len(text) - 1.

  • Compare symmetric positions: Compare text[left] with text[right].

  • Stop on a mismatch: If they differ, the string is not a palindrome.

  • Move inward: Otherwise, increment left and decrement right.

  • Finish: If left >= right, every symmetric pair matched, so the string is a palindrome.

This approach does not create a reversed copy and does not mutate the input.

Time and Space Complexity

  • Best-case time: O(1) when the first compared pair differs.

  • Average-case time: O(n) under the conventional interview assumption that a linear-length matching prefix may be examined; a tighter expected bound depends on the character distribution.

  • Worst-case time: O(n) when every symmetric pair matches.

  • Extra space: O(1), excluding the input itself. Only two integer pointers are used, and there is no recursion stack.

Here, n is the number of Unicode code points in the Python string.

Edge Cases to Consider

  • Empty input: Returns True because there are no mismatching positions.

  • One element: Returns True because the single character matches itself.

  • Duplicates: Repeated characters do not change the algorithm; "abba" is a palindrome, while "abca" is not.

  • Negative numbers: A minus sign is an ordinary character; "-121" is not a palindrome, while "-121-" is.

  • Already sorted input: Sorting is irrelevant to palindrome detection.

  • Disconnected graphs or cycles: Not applicable to strings.

  • Unicode: Python str indexing and len() operate on Unicode code points. The algorithm does not compare user-perceived grapheme clusters.

Step-by-Step Walkthrough

For "racecar":

  1. left = 0, right = 6: compare 'r' with 'r'; they match.

  2. left = 1, right = 5: compare 'a' with 'a'; they match.

  3. left = 2, right = 4: compare 'c' with 'c'; they match.

  4. left = 3, right = 3: the pointers meet, so return True.

Code Example

def is_palindrome(text: str) -> bool:
    """Return whether text is an exact palindrome by Unicode code point."""
    left: int = 0
    right: int = len(text) - 1

    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1

    return True


print(is_palindrome("racecar"))  # Expected output: True

Common Pitfalls

  • Off-by-one errors: Use left < right so the middle character of an odd-length string is not compared twice.

  • Normalization: Do not ignore case, spaces, or punctuation unless the question explicitly requires it.

  • String construction: Python strings are immutable, and repeated += in a loop can take O(n²) time. The two-pointer solution avoids constructing another string.

  • Slicing cost: text == text[::-1] is concise, but text[::-1] creates an O(n) copy, so it does not have O(1) extra space.

  • Recursion: The iterative solution avoids recursion-depth concerns.

26

How can you generate all permutations of a string?

Backtracking generates every permutation by selecting one unused character at each level and recursively exploring that choice. The default implementation returns distinct permutations in lexicographic order; unique=False returns all positional permutations, including duplicate strings.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Sort the characters so identical characters are adjacent and distinct results are generated lexicographically.

  2. Track which character positions have been used.

  3. Add one unused character to the current path and backtrack.

  4. When the path contains every character, join it into a completed permutation.

  5. For distinct results, skip a repeated character when an earlier identical character is still unused. This prevents equivalent choices at the same recursion level.

The used array tracks positions rather than characters, so repeated characters are handled correctly.

Example Walkthrough

For "aab", the distinct results are:

Selected path Completed result
a → a → b "aab"
a → b → a "aba"
b → a → a "baa"

The second "a" is skipped when the first "a" is available at the same recursion level, preventing duplicate results such as "aab" from appearing twice.

Code Example

def string_permutations(text: str, *, unique: bool = True) -> list[str]:
    """Return all permutations of text, optionally removing duplicate strings."""
    characters = sorted(text)
    used = [False] * len(characters)
    path: list[str] = []
    results: list[str] = []

    def backtrack() -> None:
        if len(path) == len(characters):
            results.append("".join(path))
            return

        for index, character in enumerate(characters):
            if used[index]:
                continue

            # Skip equivalent choices at the same recursion level.
            if (
                unique
                and index > 0
                and characters[index] == characters[index - 1]
                and not used[index - 1]
            ):
                continue

            used[index] = True
            path.append(character)

            backtrack()

            path.pop()
            used[index] = False

    backtrack()
    return results


print(string_permutations("aab"))
# ['aab', 'aba', 'baa']

Complexity

Let n be the number of characters and P the number of returned strings.

  • Sorting: O(n) in the best case for already sorted input and O(n log n) in the average and worst cases.

  • Generation with unique=False: P = n!, and the time is Θ(n × n!), including traversal and joining the outputs.

  • Generation with unique=True: The number of distinct results is P = n! / (c₁! × c₂! × ... × cₖ!), where each cᵢ is the frequency of one repeated character. A safe, though not always tight, output-sensitive upper bound for this implementation is O(n²P): there can be O(nP) prefix states, and each scans up to n candidates. The worst case across all length-n inputs is Θ(n × n!), attained when all characters are distinct.

  • Best, average, and worst generation costs: For a fixed character multiset, these are identical because traversal depends on character frequencies rather than the original ordering. Only sorting has different best and average/worst costs.

  • Auxiliary space: O(n), including the sorted character list, used array, current path, and recursion stack. This excludes the input and returned results.

  • Output space: O(nP) for storing every completed string.

  • Total space including input and output: O(n + nP).

Common Pitfalls

  • Empty input: The function returns [""], representing the single permutation of an empty sequence.

  • One character: The result contains that character once.

  • Duplicate characters: The default avoids duplicate strings; unique=False includes permutations arising from different positions.

  • Already sorted input: The input is copied into a sorted list, but all permutations are still generated.

  • Recursion depth: The stack depth is O(n). For lengths near Python’s recursion limit, use an explicit stack or carefully raise the limit.

  • String construction: Avoid repeatedly using result += character; repeated immutable-string concatenation can become O(n²). A list plus "".join(...) is more efficient.

  • Unicode: Python str iteration works with Unicode code points, not bytes. A visible character such as an emoji may consist of multiple code points.

  • Mutation: The original string is never modified.

27

How do you check whether two strings are anagrams?

Two strings are anagrams when they contain the same characters with the same frequencies, regardless of order. A hash map can count characters in the first string and subtract those in the second.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • If the strings have different lengths, they cannot be anagrams.

  • Count each character in the first string.

  • For each character in the second string, decrement its count.

  • The strings are anagrams exactly when every remaining count is zero.

This assumes comparison is case-sensitive and whitespace and punctuation are significant. For case-insensitive comparison, normalize both strings with casefold() before counting.

Complexity

Let n and m be the lengths of the two strings, and let k be the number of distinct characters.

  • Best case: O(1) when the lengths differ; otherwise O(n + m).

  • Average case: O(n + m), because each character requires a constant-time average hash-map operation.

  • Worst case: O((n + m)^2) in a theoretical hash-table model with adversarial collisions; under the usual assumption of constant-time dictionary operations, this is O(n + m).

  • Auxiliary space: O(k) for the character-count map, excluding the input strings. No recursion stack is used. Including the inputs, total space is O(n + m).

Code Example

def are_anagrams(first: str, second: str) -> bool:
    """Return whether two strings contain identical character frequencies."""
    if len(first) != len(second):
        return False

    counts: dict[str, int] = {}

    for character in first:
        counts[character] = counts.get(character, 0) + 1

    for character in second:
        remaining = counts.get(character, 0) - 1
        if remaining < 0:
            return False
        counts[character] = remaining

    return True


print(are_anagrams("listen", "silent"))  # True
print(are_anagrams("hello", "world"))   # False

Example Walkthrough

For "listen" and "silent":

  1. After processing "listen", the counts are: text {'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1}

  2. Processing "silent" decrements each corresponding count once.

  3. Every count reaches zero, so the result is True.

The function also handles empty strings, one-element strings, duplicate characters, and strings containing different characters.

Interview Tips

  • Clarify whether comparison should be case-sensitive.

  • Decide explicitly whether spaces and punctuation are included.

  • Mention that Python len() counts Unicode code points, not encoded bytes.

  • For Unicode text, consider normalization and casefold() when the problem expects locale-independent matching.

  • A Counter can implement the same idea more concisely, but a manual dictionary makes the hashing logic explicit.

Common Pitfalls

  • Ignoring multiplicity: "aab" and "abb" have the same length but are not anagrams.

  • Using character sets instead of counts: A set detects which characters appear, not how many times they appear.

  • Changing only one string’s case: Both strings must use the same normalization rules.

  • Treating bytes and characters as identical: In Python, str operates on Unicode code points, while bytes operates on byte values.

  • Mutating the inputs: The implementation above creates a separate count map and does not modify either string.

28

How do you find the longest repeating subsequence in a string?

The longest repeating subsequence (LRS) is the longest character sequence that appears at least twice as a subsequence, with corresponding characters taken from different positions. It can be found using an LCS-style dynamic program that compares the string with itself while forbidding a match at the same index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let dp[i][j] represent the LRS length between the prefixes text[:i] and text[:j].

  • If text[i - 1] == text[j - 1] and i != j, the characters can be matched: dp[i][j] = dp[i - 1][j - 1] + 1.

  • Otherwise, discard one of the two candidates: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

  • The i != j restriction is essential. Without it, the program could incorrectly match each character with itself.

After filling the table, backtracking from dp[n][n] reconstructs one longest repeating subsequence.

Unlike a substring, an LRS does not need contiguous characters. For example, "abd" is a repeating subsequence of "aabebcdd".

Complexity and Alternatives

Approach Time Auxiliary space When to use
Generate every pair of subsequences and compare them O(n × 4ⁿ) O(n) Very small inputs or conceptual understanding
LCS-style dynamic programming O(n²) O(n²) Standard efficient solution

For the dynamic-programming solution:

  • Best, average and worst-case time: O(n²), because every cell in an n × n table is computed.

  • Auxiliary space: O(n²) for the table, plus O(n) for reconstruction.

  • Recursion stack: O(1), because reconstruction is iterative.

  • The input string is not counted in auxiliary space. Counting the returned string does not change the O(n²) overall space bound.

If only the LRS length is required, rolling rows can reduce auxiliary space to O(n), but retaining the full table makes reconstruction straightforward.

Walkthrough

For "aabebcdd", one longest repeating subsequence is "abd":

Character First occurrence Second occurrence
a 0 1
b 2 4
d 6 7

The occurrences preserve their order, although characters between them may be skipped. The corresponding indices differ, so the result satisfies the LRS definition.

Code Example

def longest_repeating_subsequence(text: str) -> str:
    """Return one longest repeating subsequence of text."""
    length = len(text)
    if length < 2:
        return ""

    # dp[i][j] is the LRS length for text[:i] and text[:j].
    dp = [[0] * (length + 1) for _ in range(length + 1)]

    for left in range(1, length + 1):
        for right in range(1, length + 1):
            if text[left - 1] == text[right - 1] and left != right:
                dp[left][right] = dp[left - 1][right - 1] + 1
            else:
                dp[left][right] = max(
                    dp[left - 1][right],
                    dp[left][right - 1],
                )

    # Reconstruct one optimal subsequence.
    characters: list[str] = []
    left, right = length, length

    while left > 0 and right > 0:
        if text[left - 1] == text[right - 1] and left != right:
            characters.append(text[left - 1])
            left -= 1
            right -= 1
        elif dp[left - 1][right] >= dp[left][right - 1]:
            left -= 1
        else:
            right -= 1

    return "".join(reversed(characters))


print(longest_repeating_subsequence("aabebcdd"))  # abd

Common Pitfalls

  • Using ordinary LCS without the index restriction: LCS of the string with itself can match every position with itself and incorrectly return the entire string.

  • Confusing subsequence and substring: A subsequence may skip characters; a substring must be contiguous.

  • Off-by-one errors: The table uses prefix lengths 0..n, while string positions are 0..n-1.

  • Unicode assumptions: Python str indexing and len() operate on Unicode code points, not bytes or user-perceived grapheme clusters.

  • Edge cases: Empty and one-character inputs return ""; repeated characters are handled by the same recurrence. Negative numbers, sorted numeric inputs, disconnected graphs and cycles are not applicable to this string problem.

  • Common follow-up: Interviewers may ask for the LRS length using O(n) space, the actual subsequence, or a comparison with the longest repeating substring.

29

How do you find the shortest palindrome by prepending characters?

Shortest palindrome construction depends on finding the longest palindromic prefix of the input string. If that prefix has length L, prepend the reverse of the remaining len(s) - L characters.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a string s, write it as:

s = palindromic_prefix + remaining_suffix

The result is:

reverse(remaining_suffix) + s

Choosing the longest palindromic prefix minimizes the number of characters added at the beginning.

We can find that prefix in linear time using the KMP prefix function:

  1. Build s + separator + reverse(s).

  2. Use a separator that cannot occur in the input.

  3. Compute the prefix function.

  4. The final prefix-function value is the length of the longest palindromic prefix of s.

The prefix function pi[i] stores the length of the longest proper prefix of sequence[:i+1] that is also its suffix. Because the separator occurs only once, the final value cannot incorrectly cross the boundary between s and reverse(s).

Approach Comparison

Approach Time Auxiliary space When to use
Test every prefix for being a palindrome O(n²) O(1) Small inputs or conceptual explanation
KMP prefix function O(n) O(n) General interview solution

Walkthrough

For s = "aacecaaa":

  1. reverse(s) is "aaacecaa".

  2. The combined sequence is "aacecaa" + separator + "aaacecaa".

  3. The final KMP prefix value is 7, so the longest palindromic prefix is "aacecaa".

  4. The remaining suffix is "a".

  5. Prepending its reverse produces "a" + "aacecaaa" = "aaacecaaa".

Only one character was added, and the result is a palindrome.

Code Example

def shortest_palindrome(text: str) -> str:
    """Return the shortest palindrome formed by prepending characters to text."""
    if not text:
        return ""

    # A unique object avoids collisions with any character in text.
    separator = object()
    sequence: list[str | object] = [
        *text,
        separator,
        *reversed(text),
    ]

    prefix_function = [0] * len(sequence)
    matched = 0

    for index in range(1, len(sequence)):
        while matched > 0 and sequence[index] != sequence[matched]:
            matched = prefix_function[matched - 1]

        if sequence[index] == sequence[matched]:
            matched += 1

        prefix_function[index] = matched

    longest_palindromic_prefix = prefix_function[-1]
    remaining_suffix = text[longest_palindromic_prefix:]

    return remaining_suffix[::-1] + text


# Expected output: "aaacecaaa"
print(shortest_palindrome("aacecaaa"))

Complexity and Edge Cases

Let n = len(text).

  • Best-case time: O(n), because the sequence construction and prefix-function computation are linear.

  • Average-case time: O(n), with no dependence on character distribution.

  • Worst-case time: O(n), since each prefix-function comparison is amortized constant time.

  • Auxiliary space: O(n) for the combined sequence and prefix-function array. The input string is not counted; the returned string also occupies O(n) space.

  • Recursion stack: O(1), because the implementation is iterative.

  • Empty input: Returns "".

  • One character: Returns the original string.

  • Already palindromic input: Returns the original string without additions.

  • Duplicate characters: Work normally; for example, "aaaa" is already a palindrome.

  • Unicode: Python str and len operate on Unicode code points, not bytes or necessarily user-perceived grapheme clusters.

  • Numeric values, sortedness, disconnected graphs and cycles are not applicable to this string problem.

Common Pitfalls

  • Using the wrong prefix: The required prefix is palindromic, whereas many classic problems find a longest palindromic suffix.

  • Choosing an unsafe delimiter: A literal separator such as "#" could already occur in the input. A unique object avoids that collision.

  • Incorrect slicing: After obtaining L, the characters to prepend come from text[L:], not text[:-L].

  • Repeated string concatenation: Avoid result += character inside a loop because immutable Python strings can make that O(n²). Use a list and ''.join(...) when many pieces must be combined.

  • Interview follow-ups: Be ready to explain the prefix function, distinguish this problem from longest palindromic substring, state the complexity, and discuss why Unicode normalization can affect palindrome semantics.

30

Reverse the order of words in a string.

To reverse the order of words (not the characters inside them), split the string into words, reverse that list and join it with single spaces: "the sky is blue" becomes "blue is sky the". In Python that is " ".join(reversed(text.split())), which is O(n). In an interview, also show the classic reverse-everything-then-each-word trick, which runs in O(1) extra space on a mutable character array.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Two Ideas

  • Scan and collect: walk the string from right to left, skip spaces, and slice out each word. Joining the slices gives the answer and naturally collapses repeated, leading and trailing spaces.

  • Double reversal: reverse the whole character array ("eulb si yks eht"), then reverse each word back ("blue is sky the"). Every character moves twice and no second array is needed. This is the answer for C, C++ or Java char[], where strings can be edited in place.

Approaches

Approach Time Extra space When to use
" ".join(reversed(text.split())) O(n) O(n) Idiomatic Python
Right-to-left scan with slices O(n) O(n) for the result When asked not to use split()
Double reversal on a list[str] O(n) O(1) beyond the list Mutable character arrays, “in place” requirement
Prepending each word with + O(n²) O(n) Never; each concatenation copies the result so far

Python strings are immutable, so any Python answer builds a new string of size O(n). The in-place version works on a list of characters that the caller already owns. Best, average and worst case are the same: every character is visited a constant number of times. Neither function recurses.

Code Example

def reverse_words(text: str) -> str:
    """Return the words of text in reverse order, separated by single spaces."""
    words: list[str] = []
    end = len(text)
    while end > 0:
        while end > 0 and text[end - 1].isspace():
            end -= 1
        start = end
        while start > 0 and not text[start - 1].isspace():
            start -= 1
        if start < end:
            words.append(text[start:end])
        end = start
    return " ".join(words)


def reverse_words_in_place(chars: list[str]) -> None:
    """Reverse word order in a list of characters whose words are separated by single spaces."""

    def reverse(left: int, right: int) -> None:
        while left < right:
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1

    reverse(0, len(chars) - 1)
    start = 0
    for i in range(len(chars) + 1):
        if i == len(chars) or chars[i] == " ":
            reverse(start, i - 1)
            start = i + 1


print(reverse_words("  the sky   is blue "))  # blue is sky the
letters = list("the sky is blue")
reverse_words_in_place(letters)
print("".join(letters))  # blue is sky the

Walkthrough of the Double Reversal

Step Character array
Start the sky is blue
Reverse all eulb si yks eht
Reverse word 1 blue si yks eht
Reverse word 2 blue is yks eht
Reverse word 3 blue is sky eht
Reverse word 4 blue is sky the

Edge Cases

  • Empty string or only spaces: reverse_words returns "".

  • One word: returned unchanged (without surrounding spaces).

  • Multiple, leading or trailing spaces: collapsed by the scan; the in-place version assumes single spaces, so normalise first if the input may contain more.

  • Punctuation: stays attached to its word ("hello, world" → "world hello,"), which is usually what the problem expects; say so.

  • Unicode: isspace() also recognises tabs, newlines and non-breaking spaces; the in-place version only checks " ".

Common Pitfalls

  • Reversing characters instead of words (text[::-1] gives "eulb si yks eht").

  • text.split(" ") instead of text.split(): the former keeps empty strings for repeated spaces, so the output gets extra spaces.

  • Building the result with result = word + " " + result in a loop, which is O(n²).

  • Off-by-one errors in the word loop: the final word has no space after it, which is why the loop runs to len(chars) inclusive.

  • Common follow-ups: keep the original spacing, reverse words in place with O(1) extra space, or rotate a sentence by k words using the same reversal trick.

31

How do you reverse every word in a sentence while preserving whitespace?

Reverse each contiguous sequence of non-whitespace characters without changing the word order or the original whitespace. The two-pointer approach processes each word from both ends while preserving every space, tab, and newline in its original position.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Collect the characters of the current word into a list.

  • When whitespace is encountered, append the word’s characters in reverse order, then append the whitespace unchanged.

  • Reverse any remaining word after processing the final character.

  • Join the result into a string.

Because Python strings are immutable, accumulating characters in a list and calling join() avoids the potentially quadratic cost of repeated string concatenation.

Complexity

Let n be the number of characters in the sentence.

  • Time: O(n) — each character is processed and copied only a constant number of times.

  • Auxiliary space: O(n) — the result list, current-word list, and final joined string store up to O(n) characters. The input string is not counted.

  • Best, average, and worst case: O(n) in all cases.

Code Example

def reverse_words_preserving_whitespace(sentence: str) -> str:
    """Reverse each word while preserving all whitespace and word order."""
    result: list[str] = []
    word: list[str] = []

    for character in sentence:
        if character.isspace():
            result.extend(reversed(word))
            word.clear()
            result.append(character)
        else:
            word.append(character)

    result.extend(reversed(word))
    return "".join(result)


example = "one  two\tthree\nfour"
print(repr(reverse_words_preserving_whitespace(example)))
# Output: 'eno  owt\teerht\nruof'

Example Walkthrough

For "one two":

Step Input character Result so far Current word
1 o "" o
2 n "" on
3 e "" one
4 space "eno " ""
5 space "eno " ""
6 t "eno " t
7 w "eno " tw
8 o "eno " two

The final word is reversed when the loop ends, producing "eno owt".

Edge Cases

  • Empty input: Returns an empty string.

  • Whitespace-only input: Returns the original whitespace unchanged.

  • One word: Reverses its characters without adding whitespace.

  • Repeated spaces: Preserves the exact number and positions of spaces.

  • Tabs and newlines: Preserved because str.isspace() recognizes them as whitespace.

  • Unicode: Characters are reversed by Unicode code point; combining marks may not form a visually reversed grapheme cluster.

Common Pitfalls

  • Do not use sentence.split() and " ".join() if exact whitespace must be preserved; that approach collapses repeated whitespace and removes leading or trailing whitespace.

  • Do not reverse the entire sentence, because that would also reverse word order.

  • Avoid repeated result += character in a loop: Python strings are immutable, so this can become O(n²). Use a list and join().

  • Interviewers may ask how the solution handles consecutive whitespace, Unicode, or an empty string.

32

What is the minimum append/delete cost to transform one string into another?

The longest common subsequence (LCS) determines the minimum number of insertion/deletion operations when a character may be inserted at any position and another may be deleted at any position. If the source and target lengths are n and m, and the LCS length is L, the minimum cost is n + m - 2L.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Characters that are not deleted must remain in the same relative order in both strings. Therefore, the characters preserved during the transformation form a common subsequence. To minimize deletions and insertions, preserve an LCS.

The LCS recurrence is:

  • If the current source and target characters match, extend the LCS of the preceding prefixes by one.

  • Otherwise, take the better result from skipping either the current source character or the current target character.

For example, with source = "abc" and target = "adc":

Step Operation Result
1 Find an LCS "ac"
2 Delete "b" "ac"
3 Insert "d" between "a" and "c" "adc"

Here, L = 2, so the cost is 3 + 3 - 2 * 2 = 2.

Why the Formula Is Optimal

Any valid transformation preserves some common subsequence of the two strings. If the preserved subsequence has length k, the transformation must delete at least n - k characters and insert at least m - k characters. Its total cost is therefore at least:

n + m - 2k

This bound is minimized when k is the LCS length. Keeping an LCS and deleting or inserting the remaining characters achieves that bound.

Complexity

For source length n and target length m, the standard rolling-row LCS dynamic program has the following bounds:

Case Time Extra space Reason
Best O(nm) O(min(n, m)) It examines the character pairs regardless of their distribution.
Average O(nm) O(min(n, m)) Runtime does not depend on the input distribution.
Worst O(nm) O(min(n, m)) Every pair of positions may require a comparison.

Two DP rows are live at once, each containing O(min(n, m)) entries. The input strings are not counted as extra space, and no recursion stack is used.

Common Pitfalls

  • Wrong operation model: Ordinary edit distance may also replace characters. Here, replacement is not allowed, so replacing one character requires one deletion plus one insertion.

  • Empty input: An empty source requires len(target) insertions, while an empty target requires len(source) deletions.

  • One-element input: Equal one-character strings cost 0; different one-character strings cost 2 because replacement is unavailable.

  • Duplicates: The LCS recurrence handles repeated characters correctly and does not assume unique characters.

  • Character versus byte semantics: Python str indexes Unicode code points, and len counts code points—not bytes or user-perceived grapheme clusters.

  • Appending only at the end: If insertion is restricted to the end, the LCS formula does not apply. The permitted operation model must be stated explicitly.

  • Interview follow-ups: Common follow-ups include reconstructing the actual edit sequence, handling very long strings, and comparing this approach with ordinary edit distance.

33

How to reverse a string in place without extra buffer space?

In-place string reversal uses two pointers to swap characters from opposite ends until they meet. It requires a mutable character sequence; Python’s built-in str is immutable, so reversing a Python string directly without additional storage is not possible.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Idea

For a mutable sequence such as a character array or list:

  1. Place left at the first character.

  2. Place right at the last character.

  3. Swap characters[left] and characters[right].

  4. Move left forward and right backward until left >= right.

This modifies the existing sequence without allocating another sequence proportional to its size.

Complexity

Representation Best, Average, and Worst Time Auxiliary Space
Existing mutable character list O(n) because approximately n / 2 pairs are swapped O(1), excluding the mutable input list; there is no recursion, so the recursion stack is O(1)
Python str converted with list(s) O(n) for conversion, swapping, and joining O(n) for the temporary list; the returned string also occupies O(n) space

The original Python string is not counted as auxiliary space, but the copied character list must be counted.

Edge Cases and Walkthrough

  • Empty sequence: No swaps are required.

  • One character: The character remains unchanged.

  • Duplicates: Every occurrence is preserved, although its position may change.

  • Negative-number text: "-123" becomes "321-" because every character is reversed.

  • Already sorted or palindromic input: The same swaps are still performed because the algorithm does not need to inspect whether the sequence is symmetric.

  • Unicode: Python string indexing operates on Unicode code points (including any isolated surrogate code points). Reversing code points does not necessarily preserve user-perceived grapheme clusters, which can consist of multiple code points.

For ['a', 'b', 'c', 'd']:

Step Action Result
1 Swap indices 0 and 3 ['d', 'b', 'c', 'a']
2 Swap indices 1 and 2 ['d', 'c', 'b', 'a']
3 Stop because the pointers have crossed ['d', 'c', 'b', 'a']

Code Example

def reverse_characters_in_place(characters: list[str]) -> None:
    """Reverse a mutable character list in place using two pointers."""
    left = 0
    right = len(characters) - 1

    while left < right:
        characters[left], characters[right] = (
            characters[right],
            characters[left],
        )
        left += 1
        right -= 1


characters = list("abcd")
reverse_characters_in_place(characters)
print("".join(characters))  # Output: dcba

Common Pitfalls

  • Python string immutability: text[0] = "x" is invalid. Converting the string to a list permits swapping, but that conversion requires O(n) space.

  • Incorrect space accounting: Do not describe list(s) as constant space merely because it replaces the result-building buffer.

  • Off-by-one error: Use left < right. Using left <= right swaps the middle character with itself unnecessarily, although that alone does not change the result.

  • Slicing: s[::-1] returns a new string and uses O(n) space; it is not an in-place operation.

  • Repeated concatenation: Building a result with += in a loop can take O(n²) time because Python strings are immutable.

  • Recursion: The iterative implementation has no recursion-depth risk.

34

Why is string sorting different, and how can it be optimized?

String sorting differs mainly because strings are variable-length sequences whose comparisons may inspect a long common prefix and whose ordering can depend on Unicode or locale-specific rules. Optimization therefore requires choosing the correct comparison key and algorithm while accounting for both key construction and character-comparison costs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why String Sorting Is Different

  • Variable-cost comparisons: Comparing fixed-width numbers is O(1), while comparing strings can require examining their entire common prefix. For strings of maximum length L, one comparison costs up to O(L). Arbitrary-precision integer comparisons similarly depend on the number of digits.

  • Lexicographic ordering: Characters are compared from left to right. If one string is a prefix of another, the shorter string normally comes first.

  • Multiple ordering definitions: Python’s default order compares Unicode code points, but applications may require case-folded, locale-aware, normalized, or byte-level ordering.

  • Immutable strings: Changing or extending a string creates a new string value. Repeated operations such as text += item in a loop can therefore become O(n²). Sorting itself only reorders references to the immutable strings.

  • Memory sensitivity: Long keys, temporary slices, and copied substrings can consume substantial space even when the comparison algorithm is efficient.

Choosing the Correct Ordering

Requirement Recommended approach Important detail
Exact code-point order sorted(values) Case-sensitive and deterministic
Case-folded order sorted(values, key=str.casefold) casefold() handles more Unicode cases than lower()
Locale-aware human ordering locale.strxfrm as the key The process locale, specifically LC_COLLATE, must first be configured correctly
Byte-level ordering Sort bytes values Byte order is not the same as Unicode character order

Case folding can expand a string—for example, "ß" becomes "ss"—and may cause otherwise different strings to compare as equal. Python’s stable sort preserves their original relative order.

Time and Space Complexity

Let n be the number of strings, L the maximum key length, and σ the alphabet size.

Approach Best case Average case Worst case Auxiliary space
Built-in lexicographic sort O(nL) O(nL log n) O(nL log n) O(n)
Sort with str.casefold keys O(nL) O(nL log n) O(nL log n) O(n) references plus up to O(nL) key data
Fixed-alphabet radix sort O(nL + σL) O(nL + σL) O(nL + σL) O(n + σL) for per-level buckets

The logarithmic factors come from the number of comparisons, while L accounts for character inspection. The radix-sort bound assumes a straightforward implementation over a fixed-width alphabet, such as bytes.

The input itself is not counted in auxiliary space. Python’s built-in sort uses O(n) temporary references and an O(log n) internal merge stack; computed key data is also auxiliary space.

Optimization Strategies

  • Use sorted or list.sort: Python uses Timsort, which is stable and performs well on already sorted, reversed, or partially ordered data.

  • Compute keys once: A key function is evaluated once per element, avoiding repeated expensive transformations during comparisons.

  • Prefer stable sorting: It makes duplicate handling predictable and preserves input order for equal keys.

  • Avoid unnecessary copies: Slicing a string creates an O(k) copy. Do not create substrings as keys unless the substring defines the required ordering.

  • Consider radix sorting selectively: It can approach O(nL) when the alphabet is small and the format is fixed, but Python’s built-in sort is usually simpler and often faster in practice.

  • Do not build strings with += in a loop: Collect fragments in a list and use ''.join(parts).

  • Choose the correct mutation behavior: list.sort() rearranges the list in place, whereas sorted() returns a new list.

Optimization Example

For a case-folded ordering of "pear", "Apple", "apple", and "fig":

  1. The original values are "pear", "Apple", "apple", and "fig".

  2. Their case-folded keys are "pear", "apple", "apple", and "fig".

  3. Sorting by those keys places the two equal-key values first, followed by "fig" and "pear".

  4. Stability keeps "Apple" before "apple".

Key construction costs O(nL). The total cost is O(nL) when already ordered and O(nL log n) on average and in the worst case. Empty input produces an empty result; one-element input is unchanged; duplicates retain their input order; and empty strings remain valid keys that precede longer strings sharing their prefix.

Common Pitfalls

  • Assuming string comparison is always O(1).

  • Using lower() when full Unicode case folding is required.

  • Ignoring locale configuration when using locale.strxfrm.

  • Normalizing strings without deciding whether visually equivalent Unicode sequences should compare equally.

  • Building strings through repeated concatenation.

  • Assuming equal sort keys should be reordered; stable sorting preserves their original order.

  • Confusing Python code-point ordering with byte ordering.

  • Using list.sort() when the original list must remain unchanged.

35

What is the longest common prefix algorithm and where is it used?

The longest common prefix (LCP) is the longest string that appears at the beginning of every input string. The standard algorithm checks characters at the same position across all strings and stops at the first mismatch.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Two common strategies are vertical scanning and horizontal pairwise scanning. The following steps describe vertical scanning:

  1. Find the length of the shortest string, since the common prefix cannot be longer than it.

  2. Compare the character at index 0 across every string.

  3. Continue comparing characters at index 1, 2, and so on.

  4. Stop at the first index where the characters do not all match.

  5. Return the matching prefix.

For example:

Index flower flow flight Result
0 f f f Continue
1 l l l Continue
2 o o i Stop

The answer is "fl".

Relevant edge cases include:

  • Empty collection: Return "".

  • Any empty string: Return "".

  • One string: Return that string.

  • Duplicate strings: They are handled normally.

  • Unicode: Python string indexing operates on Unicode code points, not bytes or user-perceived characters.

Applications

  • Autocomplete and typeahead systems: Filter candidates that begin with the user’s current input.

  • File and directory hierarchies: Identify the deepest lexically shared path among several locations.

  • Batch processing: Find a common naming prefix before applying a transformation to related records.

  • String grouping: Group records by a shared prefix, such as product families or geographic regions.

  • Trie implementations: During insertion, matching characters can reuse an existing trie path. In a compressed or radix trie, two keys share an explicit path segment that ends where their edges diverge.

  • Version and configuration management: Detect shared prefixes in configuration keys or versioned names.

Complexity

Let:

  • n be the number of strings.

  • m be the length of the shortest string.

  • L be the length of the returned prefix.

  • S be the total number of characters across all strings.

  • P be the number of matching positions before the algorithm stops.

For more than one string:

  • Best-case time: O(n): Finding the shortest length and detecting a mismatch at the first character require linear work in the number of strings.

  • Average-case time: O(n(1 + E[P])): The exact average depends on the input distribution. For comparable-length strings with long shared prefixes, this is commonly summarized as O(nm).

  • Worst-case time: O(n(m + 1)): Every string shares the entire shortest string. This is O(nm) when m >= 1 and O(n) when the shortest string is empty.

  • Overall upper bound: O(n + S): The minimum-length pass costs O(n), while character comparisons are bounded by the available input characters.

  • Auxiliary space: O(1), excluding the input and returned string. There is no recursion stack.

  • Output space: O(L) when Python slicing is used to construct the returned prefix. The input itself is not counted.

Common Pitfalls

  • Off-by-one errors: Only indices below the shortest string’s length can be examined.

  • Confusing bytes with characters: Python len counts Unicode code points, while UTF-8 storage size is measured in bytes.

  • Repeated concatenation: Avoid building the result with prefix += character in a loop because immutable strings can make that O(L²). Construct the substring once instead.

  • Assuming equal-length inputs: Use the shortest string as the upper bound.

  • Mutating the input: A read-only LCP implementation does not modify the supplied strings.

  • Common follow-up question: Interviewers may ask about finding the LCP of two strings, many strings, or using the result to implement autocomplete with a trie.

36

How do you group anagrams in an array of strings?

A character-frequency signature groups strings efficiently: two Python strings are anagrams when they contain the same Unicode code points with the same multiplicities. Store each signature as a key in a dictionary whose value contains all matching strings.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

For each string:

  1. Count the occurrences of each character with Counter.

  2. Convert the character-count mapping into a hashable frozenset of (character, count) pairs.

  3. Append the string to the group associated with that signature.

For example, the character counts {"e": 1, "a": 1, "t": 1} become:

frozenset({("e", 1), ("a", 1), ("t", 1)})

A frozenset is independent of iteration order, so equivalent frequency mappings produce equal keys.

Approach Time Space Including Output When to Use
Pairwise frequency comparisons O(n²(L + 1)) O(n + A) Very small inputs
Sorted-character signatures O(n + C log(L + 1)) O(n + C) A simple canonical representation is preferred
Frequency-signature hash map O(n + C) average O(n + C) Efficient grouping of general strings

Here, n is the number of strings, C is the total number of characters, L is the maximum string length, and A is the maximum number of distinct characters in one string.

Example Walkthrough

For ["eat", "tea", "tan", "ate", "nat", "bat"]:

String Character Counts Group
eat {e: 1, a: 1, t: 1} 1
tea {e: 1, a: 1, t: 1} 1
tan {t: 1, a: 1, n: 1} 2
ate {e: 1, a: 1, t: 1} 1
nat {t: 1, a: 1, n: 1} 2
bat {b: 1, a: 1, t: 1} 3

The result is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Code Example

from collections import Counter


def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group strings with identical character frequencies."""
    groups: dict[frozenset[tuple[str, int]], list[str]] = {}

    for word in words:
        # Exact, order-independent representation of the character counts.
        signature = frozenset(Counter(word).items())

        # Preserve duplicates and original relative order.
        groups.setdefault(signature, []).append(word)

    return list(groups.values())


words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# Expected output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Complexity

  • Best time: O(n + C), assuming no significant hash-map collisions.

  • Average time: O(n + C). Counting and signature construction are linear in the input size, while dictionary lookups have expected constant-time behavior.

  • Worst time: O(C + n²A) under pathological hash collisions, a loose bound where each lookup may compare against O(n) signatures and each comparison may inspect O(A) character-count pairs.

  • Auxiliary space: O© for retained signatures, excluding the input and returned result.

  • Output space: O(n) string references; the original string contents are not copied.

  • Recursion stack: O(1), because the implementation is iterative.

Common Pitfalls

  • Empty input: An empty list correctly returns [].

  • One element: A one-element list returns a group containing that string.

  • Duplicates: Equal strings are valid anagrams and should remain in the result. This implementation preserves them.

  • Empty strings: All empty strings share the empty signature and are grouped together.

  • Unicode normalization: Python strings contain Unicode code points. Canonically equivalent forms such as "é" and "e\u0301" are not grouped unless both are normalized first.

  • Case sensitivity: "Listen" and "silent" are not grouped because uppercase and lowercase characters are distinct.

  • Numeric-looking strings: Characters such as - and digits are compared normally, so "-1" and "1-" are anagrams.

  • Input mutation and ordering: The function does not modify the input. Groups appear in first-seen order, and strings within each group retain their input order; an already sorted input does not change this behavior.

37

How do you compare version number strings in Python?

For dotted numeric versions, perform component-wise numeric comparison rather than comparing the complete strings lexicographically. This ensures that "1.10" is correctly considered newer than "1.2".

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Comparison Rules

Split each version on ., then compare corresponding components from left to right.

  • The first unequal numeric component determines the result.

  • If all shared components are equal, the longer version is greater unless its extra components are zero.

  • This implementation treats missing trailing components as zero, so "1.2" and "1.2.0" compare as equal.

Approach Example Result
Raw string comparison "1.10" versus "1.2" Incorrect: "1.10" < "1.2"
Component-wise numeric comparison "1.10" versus "1.2" Correct: "1.10" > "1.2"
SemVer-aware comparison "1.0.0-alpha" versus "1.0.0" Prerelease is lower

The function below implements a dotted-numeric convention rather than strict SemVer. Under SemVer 2.0.0, a release has exactly three numeric core components, and leading zeroes are forbidden except for zero itself. A prerelease ranks below the corresponding release. Prerelease identifiers are compared from left to right: all-numeric identifiers compare numerically, non-numeric identifiers compare in ASCII lexicographic order, and a numeric identifier ranks below a non-numeric identifier. If all preceding identifiers are equal, a prerelease with more identifiers has higher precedence. Build metadata does not affect precedence.

Complexity

Let L be the total number of characters in both versions.

  • Best, average and worst-case time: O(L). Splitting, validation, normalization and comparison scan each component a constant number of times.

  • Extra space: O(L) for the split components and normalized values. There is no recursion, so the call stack uses O(1) space, and the input strings are not counted.

  • Total space including input: O(L).

Code Example

The implementation normalizes leading zeros and compares decimal strings directly. This avoids integer-conversion limits for exceptionally long numeric components.

def compare_version_strings(left: str, right: str) -> int:
    """Return -1, 0, or 1 for two dotted numeric version strings."""

    def parse(version: str) -> list[str]:
        if not version:
            raise ValueError("version must not be empty")

        components: list[str] = []

        for component in version.split("."):
            # Only non-negative ASCII integers are supported.
            if (
                not component
                or not component.isascii()
                or not component.isdecimal()
            ):
                raise ValueError(
                    "version components must be non-negative integers"
                )

            # Remove leading zeros while preserving one zero for "0".
            components.append(component.lstrip("0") or "0")

        return components

    left_components = parse(left)
    right_components = parse(right)

    component_count = max(len(left_components), len(right_components))

    for index in range(component_count):
        left_component = (
            left_components[index]
            if index < len(left_components)
            else "0"
        )
        right_component = (
            right_components[index]
            if index < len(right_components)
            else "0"
        )

        # More digits means a larger non-negative integer.
        if len(left_component) != len(right_component):
            return -1 if len(left_component) < len(right_component) else 1

        # Equal-length decimal strings can be compared lexicographically.
        if left_component != right_component:
            return -1 if left_component < right_component else 1

    return 0


result = compare_version_strings("1.10.2", "1.9.9")
print(result)  # 1

The example proceeds as follows:

  1. Split the versions into ["1", "10", "2"] and ["1", "9", "9"].

  2. Compare the first components: "1" equals "1", so continue.

  3. Compare the second components: "10" has more digits than "9", so it is larger.

  4. Return 1, indicating that the left version is newer.

Common Pitfalls

  • Lexicographic comparison: Comparing complete strings incorrectly ranks "1.10" below "1.2".

  • SemVer assumptions: Missing components are not universally equivalent to zero. Strict SemVer requires exactly three numeric core components.

  • Invalid input: Empty versions, empty components such as "1..2", negative values and nonnumeric labels are rejected by this implementation.

  • Leading zeros: This dotted-numeric implementation considers "01" equal to "1", although strict SemVer forbids leading zeroes.

  • Edge cases: One-component versions work correctly, and duplicate components compare normally. Sortedness is irrelevant, while graph concepts such as connectivity and cycles do not apply.

  • Follow-up question: Interviewers may ask how prerelease labels such as alpha, beta and rc should be ordered, which requires a SemVer-aware comparison strategy.

38

How do you encode and decode strings with Run-Length Encoding?

Run-Length Encoding (RLE) compresses consecutive repeated characters by replacing each run with its count and character. A delimiter such as # can separate the count from the character, making the format unambiguous even when the original string contains digits.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an input such as aaabbcddd, identify each maximal run:

  • aaa becomes 3#a

  • bb becomes 2#b

  • c becomes 1#c

  • ddd becomes 3#d

The encoded result is:

3#a2#b1#c3#d

To decode, repeatedly:

  1. Read the decimal count.

  2. Read the # delimiter.

  3. Read the character following the delimiter.

  4. Repeat that character count times.

The implementation below uses Python str characters, which are Unicode code points rather than bytes. Therefore, len(text) counts code points, not encoded byte length.

Complexity

Let:

  • n be the number of characters in the original string.

  • m be the length of the encoded string.

  • k be the length of the encoded output.

  • r be the number of runs.

Operation Best case Average case Worst case Reason
Encode O(n) O(n) O(n) Every input character is examined once
Decode O(m + n) O(m + n) O(m + n) Parsing takes O(m), and producing the output takes O(n)
Uncompressed copy O(n) O(n) O(n) Every character is copied without compression

Encoding uses O(k) space for the generated fragments and output, excluding the input string. Decoding uses O(n) space for the reconstructed output, excluding the encoded input. Neither implementation uses recursion, so there is no recursion-stack cost.

RLE is most effective when the input contains long consecutive runs, such as repeated spaces, repeated status characters, or simple bitmap-like data. It can make already varied data larger.

Edge Cases

  • Empty input: encode_rle("") and decode_rle("") both return "".

  • One character: "a" becomes "1#a".

  • Duplicates: Consecutive duplicates are combined, while separated duplicates remain separate runs.

  • Negative numbers: Counts are never negative; malformed encoded counts raise ValueError.

  • Digits in the original text: The # delimiter allows characters such as "7" to be encoded and decoded correctly.

  • Malformed input: Missing counts, missing delimiters, invalid characters, or non-positive counts are rejected.

  • Unicode: Characters are counted as Python code points; combining marks and emoji sequences may represent multiple code points visually.

Code Example

def encode_rle(text: str) -> str:
    """Encode consecutive characters as count#character runs."""
    if not text:
        return ""

    parts: list[str] = []
    run_character = text[0]
    run_length = 1

    for index in range(1, len(text)):
        character = text[index]

        if character == run_character:
            run_length += 1
        else:
            parts.append(f"{run_length}#{run_character}")
            run_character = character
            run_length = 1

    parts.append(f"{run_length}#{run_character}")
    return "".join(parts)


def decode_rle(encoded: str) -> str:
    """Decode a count#character run-length encoded string."""
    if not encoded:
        return ""

    parts: list[str] = []
    index = 0

    while index < len(encoded):
        count = 0
        has_digit = False

        # Parse the count without creating a slice of the encoded string.
        while index < len(encoded) and encoded[index] != "#":
            digit_character = encoded[index]

            if digit_character not in "0123456789":
                raise ValueError("Encoded count must contain only decimal digits")

            count = count * 10 + (ord(digit_character) - ord("0"))
            has_digit = True
            index += 1

        if not has_digit:
            raise ValueError("Missing run count")

        if index >= len(encoded):
            raise ValueError("Missing '#' delimiter")

        index += 1  # Skip the delimiter.

        if index >= len(encoded):
            raise ValueError("Missing encoded character")

        character = encoded[index]
        index += 1

        if count <= 0:
            raise ValueError("Run count must be positive")

        parts.append(character * count)

    return "".join(parts)


print(encode_rle("aaabbcddd"))  # Expected: 3#a2#b1#c3#d
print(decode_rle("3#a2#b1#c3#d"))  # Expected: aaabbcddd

Common Pitfalls

  • Incorrect run boundaries: A new run starts whenever the current character differs from the previous one; nonconsecutive duplicates must not be combined.

  • Off-by-one errors: The final run must be emitted after the scan, and the decoder must verify that a character exists after every #.

  • Ambiguous formats: A format such as 3a2b can be difficult to parse when the original text contains digits. A delimiter or escaping mechanism avoids ambiguity.

  • Mutating or repeatedly concatenating strings: Python strings are immutable. Using result += piece in a loop can become O(n²); accumulate fragments in a list and use "".join(parts).

  • Forgetting validation: Production decoders should reject malformed input rather than silently producing incorrect output.

  • Interview follow-up: Be ready to explain why RLE is suitable for repetitive data, how Unicode differs from byte-oriented encoding, and how you would add an escape mechanism if the delimiter itself could conflict with the chosen format.

39

How do you implement a Caesar cipher and evaluate its security?

A Caesar cipher encrypts text by shifting each ASCII letter by a fixed number of positions in the alphabet, wrapping around after Z or z. It is useful for learning substitution ciphers, but it is not secure for protecting real data.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Shift: The number of positions each letter moves. A shift of 3 maps A to D.

  • Wrapping: Modular arithmetic handles transitions such as X shifting to A.

  • Case preservation: Uppercase and lowercase letters are shifted independently.

  • Non-letters: This implementation leaves spaces, punctuation, digits, and Unicode characters unchanged.

  • Decryption: Subtract the same shift, equivalent to using (26 - shift) % 26.

Code Example

def caesar_encrypt(text: str, shift: int) -> str:
    """Encrypt ASCII letters using a Caesar shift from 0 through 25."""
    if not 0 <= shift <= 25:
        raise ValueError("shift must be between 0 and 25")

    encrypted: list[str] = []

    for character in text:
        if "A" <= character <= "Z":
            base = ord("A")
            offset = ord(character) - base
            encrypted.append(chr(base + (offset + shift) % 26))
        elif "a" <= character <= "z":
            base = ord("a")
            offset = ord(character) - base
            encrypted.append(chr(base + (offset + shift) % 26))
        else:
            encrypted.append(character)

    return "".join(encrypted)


print(caesar_encrypt("Attack at dawn!", 3))  # Tdfwh df gdzq!

Using a list and join avoids repeated string concatenation. Repeated text += character can take O(n²) time because immutable strings must be copied.

Example Walkthrough

For "abc XYZ!" with a shift of 3:

Input Operation Output
a Shift forward three letters d
b Shift forward three letters e
c Shift forward three letters f
X Wrap after Z A
Y Wrap after Z B
Z Wrap after Z C
! Leave unchanged !

The result is "def ABC!".

Security Assessment

The implementation defines 26 possible shifts, 0 through 25; if the identity shift is excluded, there are only 25 nontrivial shifts. An attacker can try every shift, so brute-force decryption takes O(25n), which is O(n) for the fixed alphabet. A dictionary or known-plaintext attack is also effective.

Security property Caesar cipher behavior Consequence
Keyspace 26 possible shifts, including the identity shift Trivial brute force
Letter frequencies Preserved Frequency analysis can reveal plaintext
Repeated patterns Preserved Known phrases help identify the shift
Determinism Equal plaintexts produce equal ciphertexts Patterns remain visible
Integrity No protection against modification Ciphertext can be tampered with undetected
Modern cryptography No authenticated encryption Unsuitable for sensitive data

It should therefore be treated as encoding or obfuscation, not real encryption. For actual applications, use a vetted cryptography library with AES-GCM or ChaCha20-Poly1305, a securely generated key, and a unique nonce for every encryption under the same key.

Complexity

For a string containing n Unicode code points:

  • Best case: O(n) — every character must be inspected.

  • Average case: O(n) — each character requires constant work.

  • Worst case: O(n) — all characters may be letters and require shifting.

  • Space: O(n) for the character list and resulting string; no recursion stack is used. The input string itself is not counted, although including it still gives O(n) total space.

Common Pitfalls

  • Edge cases: Empty input returns ""; one-character inputs and duplicate characters are handled independently; negative shifts and shifts above 25 raise ValueError.

  • Off-by-one errors: Shift 25 and shift 0 are valid; shifts outside 0..25 are rejected by this implementation.

  • Incorrect wrapping: Use % 26 when moving forward and (26 - shift) % 26 when decrypting.

  • Unicode assumptions: len counts Unicode code points, not bytes or grapheme clusters. This implementation intentionally changes only ASCII letters.

  • Inefficient concatenation: Avoid result += character in a loop; collect characters in a list and call "".join.

  • False sense of security: A Caesar cipher is intentionally simple and must not be used for passwords, financial data, private messages, or other sensitive information.

40

What challenges do Unicode encoding and decoding create for strings?

Unicode encoding maps Unicode code points to bytes, while decoding performs the reverse mapping using a particular encoding. The main challenges arise because code points, code units, bytes, and user-perceived characters are different units, and Unicode can represent the same text in multiple forms.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concepts

Unicode separates text representation into several layers:

  • Code point: A number assigned to a Unicode character, such as U+00E9 for é.

  • Code unit: A fixed-size storage unit used by some encodings. Java and JavaScript primarily use 16-bit UTF-16 code units.

  • Byte: An 8-bit unit used by physical storage and most modern text encodings.

  • Grapheme cluster: A user-perceived character, which may contain multiple code points. For example, the flag of France contains two regional-indicator code points.

Consequently, these lengths can differ:

  • Python len("é") is 1 code point.

  • The UTF-8 representation of "é" is 2 bytes.

  • Java "😀".length() is 2 UTF-16 code units.

  • A single visible character such as "é" may require multiple code points or bytes.

Main Challenges

  • Variable-length representations: UTF-8 uses one to four bytes per code point. Code must not split a multi-byte character in the middle.

  • Invalid byte sequences: Arbitrary bytes may not form valid UTF-8. Decoders can raise an exception, replace invalid data, or ignore it, but these policies have different safety implications.

  • Missing encoding metadata: A Python bytes object does not remember how it was encoded. The application must know whether the bytes represent UTF-8, UTF-16, Latin-1, or something else.

  • Canonical equivalence: Unicode has canonically equivalent sequences such as precomposed "é" (U+00E9) and decomposed "é" (U+0065 U+0301). They may look identical but have different byte representations.

  • Normalization versus encoding: Normalization changes the internal code-point sequence; encoding converts text into bytes. str.encode() does not automatically perform Unicode normalization.

  • Legacy encodings: Shift_JIS has lead/trailing-byte structure and vendor-extension compatibility issues, while legacy code pages such as GBK use different byte mappings. Neither should be assumed interchangeable with UTF-8, which is usually preferable for interchange.

  • Security concerns: Normalization differences, homoglyphs, mixed scripts, and invalid decoding can enable visually misleading text or bypass application-level validation.

Language Approaches

Language String representation Typical encoding boundary
Python 3.12 str stores Unicode code points; bytes stores raw bytes Explicit encode() and decode()
Java 21 String represents UTF-16 code units Charset APIs and byte arrays
JavaScript ES2023 Strings use UTF-16 code units Web APIs provide TextEncoder and TextDecoder; TextEncoder always emits UTF-8, while TextDecoder defaults to UTF-8 and can support other encodings in Web environments
C++20 std::string stores bytes; Unicode requires explicit string types std::u8string, std::u16string, or std::u32string

Languages generally separate Unicode text from encoded bytes, and conversion occurs at I/O boundaries, either explicitly or inside an I/O API. Strict-error policies are available in many APIs, although their defaults differ. Support for grapheme clusters also varies; iteration over code points or code units does not necessarily match user-visible characters.

Complexity

Let n be the number of Unicode code points and m the number of encoded bytes.

Operation Best Average Worst Space
UTF-8 encoding O(n) O(n) O(n) O(n) bytes including output
UTF-8 decoding O(m) O(m) O(m) O(k) including output, where k ≤ m
Strict byte validation O(m) O(m) O(m) O(1) auxiliary space

UTF-8 encoding is linear because each code point produces at most four bytes. UTF-8 decoding and validation process each input byte a constant number of times. These bounds do not differ between best, average, and worst cases. Space includes the returned object; the input is not counted, and the auxiliary space excluding that output is O(1).

Common Pitfalls

  • Do not use byte length as character length or assume one code point equals one visible character.

  • Do not decode with the wrong encoding, especially when handling HTTP data, files, or command-line arguments.

  • Prefer strict decoding at trust boundaries. Replacement-character policies can silently corrupt data and hide attacks.

  • Normalize identifiers with a documented canonical form when semantic equality matters. Normalization alone is not a complete security control because homoglyphs and mixed scripts can remain.

  • Never slice UTF-8 bytes at arbitrary indices; operate on decoded text or code-point-aware boundaries.

  • In interviews, expect follow-up questions about UTF-8 versus UTF-16, malformed input, canonical equivalence, grapheme clusters, and why a bytes object must carry encoding information separately.

41

How are Regular Expressions used for string pattern matching and validation?

A regular expression (regex) is a small pattern language that describes a set of strings. You use it in three ways: validate that a whole string has the expected shape (fullmatch), find or extract parts of a larger string (search, finditer, capture groups), and transform text (sub, split). Regex checks form, not meaning: it can confirm that 2026-02-30 looks like a date, but only a real date parser can reject it.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Building Blocks

Element Meaning Example
Literal Matches itself cat
Character class One character from a set [A-Za-z], d, s, w
Quantifier Repetition *, +, ?, {2,4}
Lazy quantifier Match as little as possible .*?
Anchor Position, not a character ^, $, b
Group Capture a part (d+), (?P<year>d{4})
Lookahead Condition without consuming (?=.*d)

Alternation picks one of several options: (?:jpg|png) accepts either extension, and (?:...) groups without capturing.

Matching Functions in Python

  • re.fullmatch(p, s): the whole string must match. Use it for validation.

  • re.match(p, s): matches only at the start; trailing junk is allowed.

  • re.search(p, s): first match anywhere.

  • re.finditer / re.findall: every non-overlapping match.

  • re.sub and re.split: replace or split on matches.

  • re.compile(p): build the pattern once and reuse it in loops.

Code Example

import re
from datetime import date

DATE_RE = re.compile(r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})", re.ASCII)
PAIR_RE = re.compile(r"(\w+)=(\w+)")


def parse_iso_date(text: str) -> date | None:
    """Validate YYYY-MM-DD with a regex, then check the calendar with datetime."""
    match = DATE_RE.fullmatch(text)
    if match is None:
        return None
    try:
        return date(int(match["year"]), int(match["month"]), int(match["day"]))
    except ValueError:
        return None


print(parse_iso_date("2026-02-28"))       # 2026-02-28
print(parse_iso_date("2026-02-30"))       # None
print(parse_iso_date("2026-02-28 junk"))  # None
print(dict(PAIR_RE.findall("user=ana role=admin")))  # {'user': 'ana', 'role': 'admin'}
print(re.sub(r"\s+", " ", "too   many\tspaces"))     # too many spaces

The date example shows the usual split of work: the regex rejects anything that is not shaped like a date, and datetime rejects February 30. The re.ASCII flag matters because in Python 3 \d also matches digits from other scripts, such as Arabic-Indic ٣.

How the Engine Matches

Python’s re is a backtracking engine. It tries the pattern left to right and, when a branch fails, backs up and tries the next option (another alternative, or one fewer repetition).

Engine type Examples Time guarantee Extra features
Backtracking Python re, Java, PCRE, JavaScript Usually O(n) for simple patterns; exponential worst case Backreferences, lookaround
Automaton (DFA/NFA simulation) RE2, Rust regex, Go regexp O(n·m) or linear in the text No backreferences

Here n is the text length and m the pattern size. Compiling costs O(m) and is cached by re. Matching usually needs O(1) to O(m) extra state, plus O(k) for each extracted group or result list.

Catastrophic Backtracking

A pattern like (a+)+$ against "aaaaaaaaaaaaaaaaaaaaaaaab" explores an exponential number of ways to split the a run before it fails. This is the basis of ReDoS (regular-expression denial of service) when users control the input. Defences:

  • Avoid nested quantifiers over the same characters ((a+)+, (.*)*).

  • Cap input length before matching.

  • Use atomic groups (?>...) or possessive quantifiers a++ (supported in Python 3.11+).

  • Use a linear-time engine for untrusted patterns or inputs.

Common Pitfalls

  • Validating with match or search, which accept a valid-looking prefix or substring. Use fullmatch.

  • Relying on ^…$: $ also matches before a trailing newline, so "abc\n" passes ^abc$.

  • Forgetting raw strings, so "\b" becomes a backspace instead of a word boundary.

  • Greedy .* swallowing too much (<.*> on <a><b> matches the whole string; <.*?> matches <a>).

  • Using regex for nested structures such as HTML or balanced brackets; use a parser.

  • Interviewers often ask you to explain the difference between match, search and fullmatch, and why a regex for email or dates should be combined with a real check.

42

How can I write a regular expression to validate email addresses?

A regular expression can validate the common syntactic form of an email address, such as alice@example.com. The pattern below supports an ASCII local part, dot-separated domain labels, common special characters, and basic length limits; it does not verify that the mailbox actually exists.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Pattern Requirements

The regular expression validates these components:

  • Local part: One or more letters, digits, or common special characters. Dots may separate local-part segments, but cannot appear consecutively or at the beginning or end.

  • Domain: One or more labels separated by dots. Labels may contain letters, digits, and internal hyphens, but cannot begin or end with a hyphen.

  • Top-level domain: Two to 63 ASCII letters.

  • Length limits: The local part is limited to 64 characters, the domain to 253 characters, and the complete address to 254 characters.

This is a practical validation pattern, not a complete implementation of every form allowed by RFC 5322.

How It Works

The pattern uses these regular-expression features:

  • +: Requires one or more characters.

  • *: Allows zero or more repetitions.

  • ?: Makes the preceding group optional.

  • (?:...): Groups alternatives without capturing them.

  • [A-Za-z0-9-]: Matches an allowed character inside a domain label.

  • fullmatch(): Ensures that the entire input matches, not merely a prefix.

For alice.smith@example.com, the match proceeds as follows:

  1. The local-part pattern consumes alice.

  2. The optional dot-separated group consumes .smith.

  3. The literal @ matches the separator.

  4. The domain pattern consumes example. as a domain label and com as the top-level domain.

  5. fullmatch() succeeds because the entire address matches.

By contrast, alice..smith@example.com and alice@-example.com are rejected.

Complexity

Let n be the length of the candidate address.

  • Best case: O(1) time for empty input or an input rejected immediately.

  • Average case: O(n) time for a typical address, because the input is scanned and matched.

  • Worst case: O(n^2) as a conservative bound for Python’s backtracking regular-expression engine on adversarial input. The implementation limits matching to addresses of at most 254 characters, so practical work is bounded.

  • Auxiliary space: O(1) for the surrounding Python code, excluding the input string. The regex engine may use O(n) backtracking state. There is no recursion stack. If the input itself is counted, total storage is O(n).

Code Example

import re

EMAIL_RE = re.compile(
    r"[A-Za-z0-9!#$%&'*+/=?^_`{|}~-]+"
    r"(?:\.[A-Za-z0-9!#$%&'*+/=?^_`{|}~-]+)*"
    r"@"
    r"(?:[A-Za-z0-9](?:[A-Za-z0-9-]{0,61}[A-Za-z0-9])?\.)+"
    r"[A-Za-z]{2,63}"
)


def is_valid_email(email: str) -> bool:
    """Validate a practical ASCII email address."""
    if len(email) > 254:
        return False

    local_part, separator, domain = email.partition("@")

    if not separator:
        return False
    if len(local_part) > 64 or len(domain) > 253:
        return False

    return EMAIL_RE.fullmatch(email) is not None


print(is_valid_email("alice@example.com"))  # True
print(is_valid_email("alice..smith@example.com"))  # False

Common Pitfalls

  • Using match() instead of fullmatch(): match() can accept a valid-looking prefix while ignoring invalid trailing characters.

  • Using only ^ and $: $ can match before a trailing newline. fullmatch() is safer for validation.

  • Assuming regex validates deliverability: A syntactically valid address may not exist, may be disabled, or may reject mail.

  • Ignoring Unicode: The pattern is ASCII-only. Internationalized domains generally need IDNA/punycode conversion, and Unicode local parts require additional rules.

  • Expecting full RFC 5322 support: Quoted local parts, comments, IP literals, and other specialized formats are intentionally excluded from this practical pattern.

  • Testing only typical addresses: Include empty input, missing @, repeated dots, leading or trailing dots, invalid domain hyphens, long local parts, and long domains in test cases.

43

How do I implement full-string wildcard regex matching with . and *?

A dynamic-programming wildcard matcher checks whether the entire input string matches a pattern where . represents one character and * represents zero or more occurrences of the immediately preceding literal character or .. This implements a restricted, regex-style wildcard syntax rather than the complete syntax supported by Python’s re module.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Pattern Semantics

  • .: Matches exactly one character.

  • *: Applies to the immediately preceding literal character or . and allows zero or more occurrences.

  • Full match: The pattern must consume the entire string, not merely a substring.

  • Literal characters: Every character other than . and * is matched literally.

  • Invalid pattern: A * without a preceding literal character or . raises ValueError.

For example, a*b matches b, ab, and aab, while .* matches every string, including an empty string.

Dynamic Programming

Let D[i][j] mean that the first i characters of the text match the first j characters of the pattern.

  • Literal or .: The current characters must match, and the preceding prefixes must also match: D[i][j] = D[i-1][j-1] and pattern[j-1] matches text[i-1].

  • *: Either the preceding character occurs zero times, or it matches the current text character while the pattern prefix remains active: D[i][j] = D[i][j-2] or (pattern[j-2] matches text[i-1] and D[i-1][j]).

The implementation stores only the previous and current pattern states, reducing memory from a full table to two rows.

Complexity and Approach Comparison

Let n be the text length and m the pattern length.

Approach Best time Average time Worst time Auxiliary space When to use
Recursive backtracking O(n+m) Input-dependent; O((n+1)^m) is an upper bound O((n+1)^m) O(m) recursion stack For explanation or a simple prototype
Dynamic programming O(m(n+1)) O(m(n+1)) O(m(n+1)) O(n+1) For predictable performance and production use

Recursive backtracking can repeatedly explore the zero-occurrence and consume-one-character branches of starred tokens, causing exponential work on ambiguous inputs; its stack holds at most one frame per pattern position. Dynamic programming scans the text once per pattern token, so its best, average, and worst times are the same. Its two Boolean rows require O(n+1) auxiliary space. Input storage is not included in these space figures.

Edge Cases and Walkthrough

  • An empty pattern matches only an empty string.

  • An empty string matches patterns such as "", a*, and .*.

  • A one-character text and pattern are handled normally.

  • Repeated characters require no special treatment.

  • Python strings are Unicode sequences, so len() counts Unicode code points; . matches one code point, not necessarily one displayed grapheme.

For text aab and pattern a*b, where dp[j] indicates whether text[:j] matches the processed pattern:

  1. Initially: [True, False, False, False].

  2. After processing a*: [True, True, True, False].

  3. After processing b: [False, False, False, True] (dp[0] becomes False because a literal cannot match an empty prefix).

  4. The final state is True, so the entire text matches.

Code Example

def is_match(text: str, pattern: str) -> bool:
    """Return whether text fully matches a wildcard pattern containing '.' and '*'."""
    text_length = len(text)
    dp = [False] * (text_length + 1)
    dp[0] = True

    pattern_index = 0

    while pattern_index < len(pattern):
        pattern_char = pattern[pattern_index]

        if pattern_char == "*":
            raise ValueError("'*' must follow a literal character or '.'")

        if pattern_index + 1 < len(pattern) and pattern[pattern_index + 1] == "*":
            # Process a literal followed by '*' as one pattern token.
            next_dp = [False] * (text_length + 1)
            next_dp[0] = dp[0]

            for text_index in range(1, text_length + 1):
                character_matches = (
                    pattern_char == "." or pattern_char == text[text_index - 1]
                )

                # Zero occurrences use dp; one more occurrence uses next_dp.
                next_dp[text_index] = dp[text_index] or (
                    character_matches and next_dp[text_index - 1]
                )

            dp = next_dp
            pattern_index += 2
        else:
            # Update backward so dp[text_index - 1] still represents
            # the state before processing the current literal.
            for text_index in range(text_length, 0, -1):
                dp[text_index] = dp[text_index - 1] and (
                    pattern_char == "." or pattern_char == text[text_index - 1]
                )

            dp[0] = False
            pattern_index += 1

    return dp[text_length]


print(is_match("aab", "a*b"))  # True

Common Pitfalls

  • Partial matching: Returning success when only a prefix matches is incorrect.

  • Invalid stars: A leading * or consecutive * characters lack a valid operand.

  • Off-by-one errors: The empty-prefix state must remain initialized correctly.

  • Unicode assumptions: len() counts code points rather than bytes or user-perceived characters.

  • Library confusion: Python’s re.fullmatch() supports much richer syntax, including character classes and other quantifiers. Use it when those features are required rather than when this restricted custom matcher is sufficient.

44

How do multilingual strings affect data storage and manipulation?

Multilingual text should be represented as Unicode, with explicit policies for encoding, normalization, character boundaries, collation, and locale-sensitive behavior. In Python 3.12, str objects contain Unicode code points, whereas bytes objects contain arbitrary byte sequences; they are not interchangeable.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Unicode and Character Boundaries

A multilingual string is not necessarily a sequence of the characters users perceive.

  • Code point: A numeric Unicode code point. Python’s len() counts code points, including any surrogate code points that may occur in an internally constructed string.

  • Unicode scalar value: A code point excluding surrogate values. Valid UTF-8 contains scalar values, not lone surrogates.

  • Grapheme cluster: A user-perceived character that may contain multiple code points. For example, é can be one code point (U+00E9) or two (e followed by U+0301).

  • Encoded bytes: The representation used for storage or transmission. UTF-8 encodes each Unicode scalar value in one to four bytes.

Consequently, lengths differ depending on whether code points, grapheme clusters, or encoded bytes are measured. Indexing and slicing a Python string operate on code points, not necessarily user-visible characters. Case conversion can also change length, such as when ß becomes SS under upper().

Storage and Data Integrity

  • Store text with a declared encoding: UTF-8 is a common storage and interchange format because it preserves the Unicode code-point sequence and is self-synchronizing. Other encodings may be required by external systems, but the encoding must be recorded.

  • Define a decoding policy: Strict decoding rejects malformed byte sequences with UnicodeDecodeError. If replacement behavior is required, use an explicit error handler and account for possible data loss.

  • Normalize at boundaries: Apply NFC during ingestion and before comparison or indexing when canonically equivalent representations such as Café and Café should be treated identically. NFKC is useful for compatibility matching but can erase distinctions between compatibility variants.

  • Define uniqueness rules: Normalize before inserting into a uniqueness constraint or creating an exact-match index if canonically equivalent values must not be stored separately.

  • Choose collation deliberately: Binary ordering, code-point ordering, and locale-aware linguistic ordering are different. Database sorting also depends on the database, encoding, and configured collation.

  • Avoid fixed-byte character assumptions: Use text or Unicode-aware database types rather than assuming one character occupies a fixed number of bytes.

  • Preserve originals when necessary: Keeping the original and normalized forms is useful for auditing, but the two representations must remain semantically consistent.

Manipulation and Complexity

Python strings are immutable, so concatenation creates a value and slicing creates a copy. Let n and m be string lengths, k be a slice’s length, and N be the total size of all parts. Extra space excludes the original input but includes newly allocated output; no recursion stack is involved.

Operation Best time Average time Worst time Extra space Reason
len(text) O(1) O(1) O(1) O(1) Python stores the string length
Iterate over text O(n) O(n) O(n) O(1) Each code point is visited once
left + right O(n + m) O(n + m) O(n + m) O(n + m) A new immutable string is allocated
text[start:end] O(1) for an empty/full-slice special case O(k) O(k) O(k) A partial slice copies k code points
Repeated text += value with copying on every append O(N) O(N²) O(N²) O(N) peak Cumulative lengths may be copied repeatedly; runtimes may optimize some cases
"".join(parts) O(N) O(N) O(N) O(N) The parts are copied once into the result

For Unicode-safe processing:

  • Use ord() and chr() for code-point arithmetic.

  • Use str.casefold() for caseless comparison when appropriate, while remembering that it is Unicode-wide rather than fully locale-aware.

  • Use unicodedata.normalize() for canonically equivalent text.

  • Use a dedicated grapheme-segmentation library when processing depends on user-perceived characters.

  • Build large strings with a list and join() rather than relying on repeated +=.

Common Pitfalls and Interview Tips

  • Assuming len() counts visible characters: It counts code points; grapheme-cluster counting requires another approach.

  • Comparing raw strings without normalization: Canonically equivalent inputs can compare unequal.

  • Slicing at code-point offsets: An offset that appears correct visually may split a grapheme cluster.

  • Using repeated string concatenation: Copying can produce quadratic time; use a list and join() for predictable performance.

  • Ignoring collation and bidirectional text: Correctly stored text can still be searched, sorted, or displayed incorrectly.

  • Mutating input unexpectedly: Transformations should generally return new values while preserving the original when required.

Interviewers commonly follow up by asking how to count user-perceived characters, compare accented text, select a database encoding, or make Unicode processing safe across an API boundary.

45

How does locale-specific sorting affect string comparison?

Locale-specific sorting orders strings according to linguistic rules for a particular language and region rather than by raw Unicode code point. These rules can affect case, accents, normalization, contractions, and the relative order of characters.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Locale-Aware Versus Code-Point Ordering

A locale-sensitive comparison uses a collation defined by settings such as language, region, and tailoring. By contrast, direct code-point ordering compares the numeric values of characters.

String behavior Code-point ordering Locale-aware ordering
Case Uses code-point values May place lowercase before uppercase
Accents Always distinguishes é from e May treat them as equal at a lower comparison strength
Normalization Requires pre-normalization Usually handles equivalent representations
Character order Fixed by Unicode Can differ by locale
Linguistic contractions Not interpreted May use locale-specific contraction rules

For example, Python compares str values by Unicode code point, not by locale:

"A" < "a"   # True

A collation for English can instead consider a and A equal except at a tertiary level. Likewise, composed "é" (é) and decomposed "é" (e followed by a combining accent) may compare differently by code point but equal under a normalized collator.

What Locale Settings Change

A locale commonly includes language, country, and optional tailoring rules. Collation behavior may also depend on:

  • Case level: Whether uppercase and lowercase letters are equivalent.

  • Accent level: Whether accents distinguish characters.

  • Normalization: Whether canonically equivalent Unicode sequences compare equally.

  • Strength: Which differences are considered primary, secondary, or tertiary.

  • Tailoring: Custom rules for a language, organization, or product.

The result can be either a simple ordering result or several comparison levels. For example, a collator might report that two strings are equal at the accent level but different at the case level.

Effects on Algorithms

Locale-aware comparison changes both the result and potentially the cost of an algorithm. For strings of length at most k:

Operation Time complexity Extra space
Code-point comparison O(k) O(1)
Typical locale-aware comparison O(k) Usually O(1)
Generate one sort key per string O(nk) typical Up to O(nk) for stored keys
Standard comparison-based sort O(kn log n) best, average, worst O(n) plus stored keys

The space figures exclude the original input. Exact collator complexity depends on the locale and implementation; some also maintain temporary state.

For a standard merge sort, the number of comparisons is O(n log n) in the best, average, and worst cases. An adaptive sort can have an O(n) best case for comparison count, but locale-key generation still takes O(nk).

Precomputing sort keys is often preferable to invoking a full collator during every comparison. Each string is transformed once, and the sort can then compare the resulting keys. This works only when the collation provides a consistent ordering and independent keys.

Other algorithms are affected as follows:

  • Binary search: Safe only if comparisons use the same total ordering used to build the collection. With locale comparisons taking O(k), search takes O(k log n).

  • Deduplication: Locale-aware equality may group strings that are not identical by code point, such as case variants.

  • Set and map keys: Choosing a locale-sensitive key can intentionally merge different spellings, but it may surprise callers expecting exact string identity.

  • Substring searches: A pattern can match according to linguistic rules rather than exact code-point sequences.

Swedish Collation Example

Consider these strings:

ä, å, a, z, ö

Code-point ordering compares the Unicode values and produces:

a, z, ä, å, ö

Under standard Swedish collation, å, ä and ö are separate letters that come after z in that order, producing:

a, z, å, ä, ö

This demonstrates why a result can be correct for one locale but incorrect for another. Changing only the locale changes the comparator’s ordering.

Common Pitfalls

  • Using raw Unicode order for user-facing lists: Users often expect locale-aware ordering, especially for names.

  • Changing locale during an operation: Sorting, searching, and deduplication must use a consistent collation.

  • Ignoring normalization: Equivalent Unicode representations can behave differently without normalization.

  • Assuming Python’s str comparison is locale-aware: Python uses code-point ordering. The locale module provides limited strxfrm support, but behavior depends on the operating system’s locale facilities; full Unicode collation generally requires an ICU-based implementation.

  • Applying locale sorting to identifiers: Stable code-point ordering is usually better for identifiers, database keys, and protocols.

  • Breaking search assumptions: A comparator must provide a consistent total preorder; inconsistent case or accent rules can cause binary search and sorting to fail.

46

How can you minimize memory usage with large strings?

Minimizing memory usage requires incremental processing: scan or transform data in bounded chunks, avoid unnecessary copies, and stream results instead of retaining every intermediate value. Python strings are immutable, so techniques that appear to modify a string in place usually create another string.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Techniques

  • Process in chunks: Read or examine a fixed number of characters at a time. This keeps temporary working memory bounded even when the total data is very large.

  • Use generators: A generator yields one result at a time, allowing callers to process data without storing a complete collection.

  • Avoid unnecessary conversions: Operations such as upper(), lower(), split(), strip(), and regular-expression findall() create new objects and may consume substantial memory.

  • Avoid repeated concatenation: Building a string with text += part in a loop can take O(n^2) time because strings are immutable. Collect fragments in a list and use ''.join(parts).

  • Be careful with slicing: text[start:end] creates a copy of the selected characters, requiring O(k) space for a slice of length k.

  • Stream large outputs: Write processed data incrementally rather than accumulating a large final string, especially when the output is sent to a file or network stream.

For truly large data, reading from a file line by line or in fixed-size blocks is usually better than first loading the entire file into one string.

Memory and Time Complexity

The following complexities distinguish auxiliary memory from the memory occupied by the original input:

Approach Time Auxiliary space When to use
One direct character scan O(n) O(1) The complete string already exists in memory
Chunked processing O(n) O(k) Temporary working memory must be bounded
split() or findall() O(n) O(n) The result set or tokens fit comfortably in memory
Building with repeated += O(n^2) worst case O(n) Avoid this pattern
Building fragments then join O(n) O(n) including output A complete final string is required

Here, n is the number of characters and k is the chunk size. If the input string itself is counted, total space is O(n+k) for chunked processing and O(n) for a direct scan. Best, average, and worst-case running time are all O(n) for a complete scan because every character may need to be examined.

Unicode and Character Boundaries

Python str values represent Unicode text, and len(text) counts Unicode code points, not bytes or user-perceived characters. An emoji may consist of multiple code points, while its UTF-8 encoding may occupy several bytes.

  • A str chunk size is measured in code points.

  • A bytes chunk size is measured in bytes.

  • Slicing a str never splits an individual code point, but it may split a multi-code-point grapheme cluster.

  • When decoding byte chunks, use codecs.getincrementaldecoder() so a multi-byte UTF-8 character split across chunk boundaries is decoded correctly.

Code Example

This implementation counts words using bounded chunks while preserving state across chunk boundaries:

from collections.abc import Iterator


def iter_chunks(text: str, chunk_size: int = 64_000) -> Iterator[str]:
    """Yield bounded-size chunks of a string."""
    if chunk_size <= 0:
        raise ValueError("chunk_size must be positive")

    for start in range(0, len(text), chunk_size):
        yield text[start:start + chunk_size]


def count_words(text: str, chunk_size: int = 64_000) -> int:
    """Count whitespace-separated words without storing all tokens."""
    word_count = 0
    inside_word = False

    for chunk in iter_chunks(text, chunk_size):
        for character in chunk:
            if character.isspace():
                inside_word = False
            elif not inside_word:
                word_count += 1
                inside_word = True

    return word_count


print(count_words("alpha  beta gamma", chunk_size=6))  # 3

For chunk_size=6, the example is processed as follows:

Chunk Characters Words found Total
1 "alpha " alpha 1
2 " beta " beta 2
3 "gamma" gamma 3

The inside_word flag prevents duplicate counting for consecutive whitespace and handles words that cross chunk boundaries.

Common Pitfalls

  • Repeated concatenation: Do not build a large result with text += fragment; use a list with ''.join(fragments) or stream the output.

  • Accidental copies: Slicing, splitting, regular-expression findall(), and case conversion allocate additional strings.

  • Ignoring Unicode boundaries: Code-point, grapheme, and byte boundaries are different; chunking bytes requires safe incremental decoding.

  • Dropping boundary state: Track continuation state such as whether a word is still open when processing chunks.

  • Trying to mutate strings: Python strings are immutable; create a new value or use a mutable buffer only when appropriate.

  • Assuming zero-copy everywhere: memoryview can avoid copying byte data, but it does not provide a mutable text string or understand Unicode boundaries.

47

How does the Flyweight Pattern reduce memory usage for strings?

The Flyweight Pattern shares one canonical string object among many consumers instead of storing separate copies of identical text. This is especially effective for large datasets containing repeated values such as status labels, category names, or error messages.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The pattern separates string data into two parts:

  • Intrinsic state: immutable content shared by every occurrence, such as "ACTIVE".

  • Extrinsic state: information that differs between occurrences, such as a record’s position, formatting, or language.

A flyweight factory maintains a pool of canonical objects. When a caller requests a string, the factory returns the existing object if equivalent content is already present.

For example, if one million records contain the label "ACTIVE", all records can reference the same string while storing their record-specific information separately. Because Python strings are immutable, sharing them cannot cause one consumer’s changes to affect another.

Memory and Complexity

Let:

  • n be the number of input strings.

  • S be their total number of characters.

  • U be the number of unique strings.

  • L be the maximum string length.

Approach Time complexity Space complexity When to use
Store every occurrence separately O(S) to construct O(S) Every value is unique or duplication is small
Canonicalize with a flyweight factory Best/average O(S + n) O(S_unique + n + U) Many repeated strings share the same content

For the flyweight approach:

  • Best and average time: O(S + n) because hashing examines the characters, and dictionary operations take average O(1) time after hashing.

  • Worst time: O(S + nUL) under adversarial hash collisions, when multiple keys may be compared and each comparison can examine up to L characters.

  • Space: O(S_unique + n + U), counting the canonical content, result references, and factory table, but not the original input.

  • If the original input remains alive, total memory is O(S + n + U); the saving is realized only after duplicate input strings can be released.

Code Example

def canonicalize_strings(values: list[str]) -> list[str]:
    """Return references to one canonical object for each distinct string."""
    pool: dict[str, str] = {}
    result: list[str] = []

    for value in values:
        canonical = pool.setdefault(value, value)
        result.append(canonical)

    return result


canonical = canonicalize_strings(["ACTIVE", "ACTIVE", "DRAFT"])
print(canonical[0] is canonical[1])  # True

The factory dictionary maps each unique value to its canonical object. Duplicate inputs then reuse the first equal object.

Common Pitfalls

  • Unbounded pools: Interning unique values such as UUIDs or request-specific messages can increase memory usage rather than reduce it.

  • Assuming all equal Python strings are already shared: Python may intern identifiers and some constant strings, but dynamically constructed strings are not guaranteed to share storage.

  • Confusing characters and bytes: Python str represents Unicode text, while bytes represents raw bytes; len(str) counts Unicode code points, not encoded bytes.

  • Ignoring the retained input: Duplicate strings are not freed until references to the original copies are released.

  • Sharing mutable wrapper state: Only immutable content should be shared. Record-specific state must remain outside the shared object.

Interview Tips

Explain that the Flyweight Pattern trades a small lookup cost for reduced object allocation and memory pressure. In Python, sys.intern can canonicalize selected strings, but it should be used selectively rather than for every dynamically generated value.

Common follow-up questions include how to bound the pool, how to handle Unicode normalization, whether equal strings are guaranteed to use the same object, and how the pattern differs from ordinary object pooling. The key distinction is that flyweights share immutable intrinsic state, while a general object pool can reuse mutable objects whose state must be reset.

48

Detect if a string has any duplicate characters without using additional data structures.

Without a set or dictionary there are three classic answers: compare every pair of characters (O(n²) time, O(1) space), sort and compare neighbours (O(n log n) time, in place only where strings are mutable), or, when the input is limited to a small alphabet such as lowercase a–z, use one integer as a bit vector (O(n) time, O(1) space). State which constraint you are assuming before you code.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approaches

Approach Time Extra space When to use
Hash set (for comparison) O(n) average O(k) When extra structures are allowed
Nested loops over all pairs O(n²) O(1) Any character set, strict “no extra memory” rule
Sort, then compare neighbours O(n log n) O(1) in C++/Java char arrays; O(n) in Python Mutable character arrays
Bit vector in one integer O(n), at most 27 steps for a–z O(1) Input known to be lowercase ASCII

Python strings are immutable, so “sort in place” is not possible: sorted(text) builds a new list of n characters. That is why the Python answer is either the nested loop or the bit vector. The input itself is not counted in these space figures, and neither approach recurses.

How the Bit Vector Works

  • Map each letter to an offset: ord(character) - ord("a") gives 0 for a and 25 for z.

  • Bit offset of the integer seen records whether that letter has appeared.

  • seen & (1 << offset) tests the bit; seen |= 1 << offset sets it.

  • 26 letters fit in one machine word in any language, so the “structure” is a single integer.

By the pigeonhole principle, a lowercase string longer than 26 characters must contain a duplicate, so the loop never runs more than 27 times. The bit-vector check is therefore O(min(n, 26)), which is O(1) for that alphabet.

Code Example

def has_duplicates_lowercase(text: str) -> bool:
    """Bit-vector check for strings made only of lowercase ASCII letters a-z."""
    seen = 0
    for character in text:
        offset = ord(character) - ord("a")
        if not 0 <= offset < 26:
            raise ValueError("expected lowercase ASCII letters only")
        bit = 1 << offset
        if seen & bit:
            return True
        seen |= bit
    return False


def has_duplicates_any(text: str) -> bool:
    """Pairwise check for any characters, using O(1) extra space."""
    for i in range(len(text)):
        for j in range(i + 1, len(text)):
            if text[i] == text[j]:
                return True
    return False


print(has_duplicates_lowercase("interview"))  # True
print(has_duplicates_lowercase("python"))     # False
print(has_duplicates_any("Ab-1b"))            # True

Walkthrough

has_duplicates_lowercase("abca"), showing the low four bits of seen:

Step Character Offset Bit tested seen after Result
1 a 0 not set 0001 continue
2 b 1 not set 0011 continue
3 c 2 not set 0111 continue
4 a 0 set 0111 True

Complexity by Case

  • Nested loops: best case O(1) when the first two characters match; worst case O(n²) when all characters are distinct, since every pair is compared (n(n−1)/2 comparisons).

  • Bit vector: best case O(1); worst case 27 iterations for valid input, then the 27th letter must repeat.

  • Sort and scan: O(n log n) in every case for a comparison sort.

Edge Cases

  • Empty string and one character: no duplicates; both functions return False.

  • Case: "Aa" has no duplicate under exact comparison. Lowercase the input first only if the problem says case does not matter.

  • Characters outside a–z: the bit-vector version raises instead of giving a silently wrong answer; use the nested loop for general text.

  • Unicode: ord() returns code points up to 0x10FFFF, so a bit vector for all of Unicode would need up to 1.1 million bits, which is no longer “no extra space”.

Common Pitfalls

  • Starting the inner loop at j = 0, which compares a character with itself.

  • Calling sorted() in Python and claiming O(1) space.

  • Using a bit vector without stating the alphabet assumption.

  • Overflow in Java or C++ when the alphabet exceeds 32 or 64 letters: switch to a long, an array of words, or the nested loop.

  • A common follow-up: “what if the input is a stream you cannot store?” Then a bit vector or set is the only option, because you cannot revisit earlier characters.

49

Check for an Isomorphic String relationship between two given strings.

Two strings are isomorphic when you can replace characters in the first to get the second, where the mapping is one-to-one: each character always maps to the same character, and no two characters map to the same one. "egg" and "add" are isomorphic (e→a, g→d); "foo" and "bar" are not, because o would need to map to both a and r. The standard solution uses two hash maps, one in each direction, and runs in O(n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Two Maps

One map (source → target) catches a character mapping to two different targets. It does not catch two characters mapping to the same target:

  • "badc" and "baba": the forward map b→b, a→a, d→b, c→a has no conflict, yet b and d both map to b.

  • The backward map (target → source) catches this: b was already claimed by b, so d cannot claim it.

Both directions must stay consistent for the strings to be isomorphic. A different-length pair is never isomorphic.

Approaches

Approach Time Extra space When to use
Compare every pair of positions (i, j) O(n²) O(1) Only to explain the definition
Two dictionaries (forward and backward) O(n) O(k) Standard interview answer
Compare first-occurrence patterns O(n) O(n) When you want a canonical “shape” to group many strings

k is the number of distinct characters, bounded by the alphabet size (O(1) for ASCII). Dictionary operations are O(1) on average, so the scan is O(n). The input is not counted in the space figure, and there is no recursion. Best, average and worst case differ only in when the loop exits early: a mismatch at index 0 stops in O(1).

Code Example

def is_isomorphic(source: str, target: str) -> bool:
    """Return True if a one-to-one character mapping turns source into target."""
    if len(source) != len(target):
        return False

    forward: dict[str, str] = {}
    backward: dict[str, str] = {}

    for left, right in zip(source, target):
        if forward.setdefault(left, right) != right:
            return False
        if backward.setdefault(right, left) != left:
            return False
    return True


def shape(text: str) -> tuple[int, ...]:
    """Pattern of first-occurrence indexes; isomorphic strings share a shape."""
    first_seen: dict[str, int] = {}
    return tuple(first_seen.setdefault(character, len(first_seen)) for character in text)


print(is_isomorphic("egg", "add"))    # True
print(is_isomorphic("foo", "bar"))    # False
print(is_isomorphic("badc", "baba"))  # False
print(shape("paper"), shape("title"))  # (0, 1, 0, 2, 3) (0, 1, 0, 2, 3)

setdefault stores the mapping the first time a character appears and returns the existing value afterwards, so one call both records and checks.

Walkthrough

is_isomorphic("badc", "baba"):

Step Pair forward after backward after Result
1 b, b {b: b} {b: b} consistent
2 a, a {b: b, a: a} {b: b, a: a} consistent
3 d, b {…, d: b} b already maps to b, not d False

Edge Cases

  • Empty strings: two empty strings are isomorphic (the loop never runs).

  • One character each: always isomorphic.

  • Different lengths: rejected before the loop.

  • Repeated characters: handled by the maps, which is the whole point of the check.

  • Identical strings: isomorphic through the identity mapping.

  • Unicode: the maps work on code points, so accented letters and emoji are handled; a character built from several code points is compared code point by code point.

Common Pitfalls

  • Using only one map, which wrongly accepts "badc" and "baba".

  • Comparing len(set(source)) == len(set(target)) alone. It is necessary but not sufficient: "aab" and "abb" both have two distinct characters, yet they are not isomorphic.

  • Using fixed 256-element arrays in Python without saying the input is assumed ASCII.

  • Follow-ups interviewers ask: group a list of words by isomorphism (use shape() as a dictionary key), or the related “word pattern” problem, where the target is a list of words instead of characters.

50

Implement a string tokenizer that splits a string on multiple delimiters.

A multi-delimiter tokenizer scans the string once and cuts a token every time it meets any delimiter from a given set. When delimiters can be longer than one character (->, ::), it must try the longest delimiter first at each position, so -> is not read as - followed by >.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Remove duplicate delimiters and sort them by length, longest first.

  2. Keep two indexes: start (where the current token began) and i (the scan position).

  3. At each i, check whether any delimiter starts there with text.startswith(delimiter, i).

  4. On a match, emit text[start:i] as a token, jump i past the delimiter and set start = i.

  5. With no match, advance i by one character.

  6. At the end, emit the remaining text[start:].

A keep_empty flag decides what happens between two adjacent delimiters ("a,,b"): keep an empty token like str.split(",") does, or skip it like str.split() does for whitespace.

Approaches

Approach Time Extra space When to use
Replace every delimiter with one, then split() O(n·d) plus a new string per pass O(n) per pass Quick scripts with a few single-character delimiters
Single scan, longest delimiter first O(n·d·L) worst case O(n) for the tokens Interviews, multi-character delimiters, full control over empties
re.split with an escaped alternation O(n·d·L) typical O(n) Production code where a regex is acceptable

Here n is the text length, d the number of delimiters and L the longest delimiter. With only single-character delimiters held in a set, the scan is O(n). Space counts the output tokens, which together hold up to n characters; the input is not counted. There is no recursion.

Code Example

import re


def tokenize(text: str, delimiters: list[str], keep_empty: bool = False) -> list[str]:
    """Split text on any of the delimiters, trying the longest delimiter first."""
    if not delimiters or any(not delimiter for delimiter in delimiters):
        raise ValueError("delimiters must be a non-empty list of non-empty strings")

    ordered = sorted(set(delimiters), key=len, reverse=True)
    tokens: list[str] = []
    start = 0
    i = 0

    while i < len(text):
        match = next((delimiter for delimiter in ordered if text.startswith(delimiter, i)), None)
        if match is None:
            i += 1
            continue
        if keep_empty or i > start:
            tokens.append(text[start:i])
        i += len(match)
        start = i

    if keep_empty or start < len(text):
        tokens.append(text[start:])
    return tokens


def tokenize_regex(text: str, delimiters: list[str]) -> list[str]:
    """Same result as tokenize(keep_empty=False), using re.split."""
    ordered = sorted(set(delimiters), key=len, reverse=True)
    pattern = "|".join(re.escape(delimiter) for delimiter in ordered)
    return [token for token in re.split(pattern, text) if token]


print(tokenize("a, b;;c->d", [",", " ", ";", "->"]))  # ['a', 'b', 'c', 'd']
print(tokenize("a,,b", [","], keep_empty=True))  # ['a', '', 'b']
print(tokenize_regex("a, b;;c->d", [",", " ", ";", "->"]))  # ['a', 'b', 'c', 'd']

re.escape matters: without it a delimiter such as . or | would be read as regex syntax.

Walkthrough

tokenize("a, b;;c->d", [",", " ", ";", "->"]):

i Character Delimiter found Token emitted New start
1 , , a 2
2 space space none (empty) 3
4 ; ; b 5
5 ; ; none (empty) 6
7 - -> c 9
end d

Edge Cases

  • Empty input: returns [], or [''] with keep_empty=True (the same as "".split(",")).

  • Only delimiters: ",,," returns [] when empties are skipped.

  • Leading or trailing delimiters: produce empty tokens only when keep_empty=True.

  • Overlapping delimiters: - and -> both listed; longest first picks ->.

  • Duplicates in the delimiter list: removed by set().

  • Unicode: indexes count code points, so a multi-code-point emoji is never a delimiter unless listed exactly.

Common Pitfalls

  • Checking short delimiters before long ones, which splits -> into two cuts.

  • Building each token with += one character at a time; slice text[start:i] once instead.

  • Forgetting the last token after the loop ends.

  • Passing raw delimiters to re.split without re.escape.

  • Interviewers often follow up with quoted fields ("a,b",c), which need a small state machine that ignores delimiters inside quotes, or with streaming input, where a delimiter can be split across two chunks.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 50 Strings answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects