Skip to content

Transform a C-Style String

Level: L3-L4 Topics: Strings, In-Place Manipulation, Two-Pass Algorithms, C/C++ Pointers

Problem Statement

You are given a C-style null-terminated string (char* str) and an integer buf_len representing the total size of the buffer (which may be larger than the string itself).

Part 1: Remove all occurrences of the character 'a' from the string, in-place. You may not allocate a new buffer or change the function signature.

Part 2: In addition to removing all 'a's, expand every 'b' into the three-character string "bee". The buffer is guaranteed to be large enough to hold the final result. You still cannot allocate a new buffer.

Function signature: void transform(char* str, int buf_len)

Background & Constraints

  • The string is null-terminated ('\0' at the end).
  • buf_len includes the null terminator.
  • For Part 2, buf_len is large enough to hold the expanded result, but the unused portion of the buffer may contain garbage.
  • You cannot allocate additional memory (no malloc, no auxiliary arrays).
  • The solution must handle all combinations of 'a' and 'b' characters correctly.

Examples

Part 1 -- Remove 'a's:

Input:  "abracadabra"
Output: "brcdbr"

Part 2 -- Remove 'a's and expand 'b's:

Input:  "abc"        (buf_len >= 5)
Output: "beec"

Input:  "baac"       (buf_len >= 5)
Output: "beec"

Input:  "bbb"        (buf_len >= 10)
Output: "beebeebee"

Hints & Common Pitfalls

  1. Part 1 is straightforward. Use a read pointer and a write pointer, both starting at position 0. Walk the read pointer forward; whenever the character is not 'a', copy it to the write pointer and advance the write pointer. Terminate with '\0'.

  2. Part 2 is where it gets tricky. A single left-to-right pass fails because expanding 'b' to "bee" overwrites characters you have not processed yet.

  3. Naive approach with "baac": If you try a single forward pass -- expand 'b' to "bee", then skip the 'a's -- the expansion of 'b' will overwrite the 'a's before you get to remove them. This produces incorrect results for inputs where 'b' appears before 'a'.

  4. Two-pass approach fails if done carelessly. If you first remove 'a's (shrinking the string) and then expand 'b's left to right, the expansion can overwrite the tail of the string you still need.

  5. Optimal two-pass strategy:

    • Forward pass: Remove all 'a's (shrinking the string). While doing so, count the number of 'b's remaining.
    • Backward pass: Calculate the final length (current_len + 2 * b_count). Start from the end of the current string and work backward toward the beginning. For each character: if it is 'b', write "eeb" backward (which reads as "bee" forward); otherwise, copy the character. Since the string shrank in the first pass and you know the buffer is large enough, the backward pass never overwrites unprocessed data.

Follow-Up Questions

  1. What happens if buf_len is not large enough for the expanded result? How would you detect this, and what should the function do?

  2. Can you solve Part 2 in a single pass (not two passes)? Under what conditions would a single-pass approach work, and when would it fail?

  3. How would you generalize this to arbitrary find-and-replace pairs (e.g., replace 'x' with "xyz" and delete 'q') all in one in-place operation?

  4. What is the time and space complexity of the two-pass solution? Can you prove that the backward pass never overwrites unprocessed input?