Explain strings, moves, and concurrency

Question

What is a string in programming languages? What fields are stored in a typical struct string and how would you implement one yourself? What is the time complexity of copying a string? How can move operations be made more efficient? In Rust, does move only modify the reference? What is the difference between a thread and an asynchronous coroutine?

Simulate String Copy and Move Costs

You are given a list of operations on named strings. Each string is represented only by its length. Compute the total number of character copies performed. Allowed operations (tokens are space-separated):

• new x n: Create/overwrite variable x with a string of length n. Cost: n (copying n characters).
• copy x y: Set x to a copy of y. Cost: len(y).
• move x y: Move y into x (x takes y's contents, y becomes empty). Cost: 0.
• concat x y z: Set x to y+z. Cost: len(y)+len(z).
• mconcat x y z: Move-concatenate y and z into x; x becomes y+z and both y and z become empty. Cost: 0. Overwriting a variable discards its previous content at no cost. For mconcat, the destination x will be different from y and z. Inputs will reference only existing variables. Return the total copy cost. Input to the function is a list of operation strings in the above formats.

Constraints

• 1 <= len(ops) <= 200000
• Variable names match [A-Za-z_][A-Za-z0-9_]*
• 0 <= n <= 10^9 for new x n
• mconcat x y z will have x distinct from y and z
• All reads reference variables that have been defined earlier
• Sum of all referenced lengths can be up to 10^12; use 64-bit or big integers
• Process should be O(len(ops)) time and O(U) space where U is number of variables

Examples

Example 1

Input: ops = ["new a 5", "copy b a", "move c b", "concat d a c", "mconcat e a c"]
Output: 20

Explanation: new a 5: +5; copy b a: +5 (total 10); move c b: +0; concat d a c: +5+5 (total 20); mconcat e a c: +0. Total = 20.

Example 2

Input: ops = ["new x 4", "move y x", "copy z x"]
Output: 4

Explanation: new x 4: +4; move y x: +0 (x becomes empty, y=4); copy z x: +0 (x is empty). Total = 4.

Hints

1. Track only lengths, not string contents.
2. Use a dictionary mapping variable names to current lengths.
3. copy and concat add the source lengths to the total cost.
4. move sets the destination length and empties the source with zero cost.
5. mconcat sets destination to sum of source lengths and empties both sources with zero cost.

Approach

Maintain a dictionary mapping each variable name to its current string length. Iterate over operations, updating lengths and accumulating copy costs. The only operations that add to the total are new (n), copy (len(y)), and concat (len(y)+len(z)). Move operations and mconcat update ownership and set sources to zero length without adding to the total.

• Time complexity: O(n), where n is the number of operations
• Space complexity: O(u), where u is the number of distinct variables