Problem 1528

Abstract / Summary

Given a string and an integer array describing group sizes, interleave characters from each group in order to form a new string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1528.py

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        result = [ None ] * len(s)
        for c, i in zip(s, indices):
            result[i] = c
        return "".join(result)
6 lines | 215 bytes | submitted December 23, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 86% (500k+ submissions).

Typical patterns to solve this problem:
  • Array
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a single method restoreString. The method receives a string s and a list of integer positions indices. Its purpose is to reconstruct a new string where each character from s is placed at the index specified by the corresponding entry in indices. The algorithm builds an intermediate list to hold characters at their target positions and finally concatenates the list into the resulting string.

Key Steps and Corresponding Code

The core logic can be broken down into three distinct operations.

Allocation of a Fixed-size Container

result = [ None ] * len(s)

A list named result is created with a length equal to the input string. Each slot is initially filled with None. This pre-allocation guarantees constant-time access for later assignments and eliminates the need for dynamic resizing during the reconstruction phase.

Placement of Characters According to the Mapping

for c, i in zip(s, indices):
    result[i] = c

The zip function pairs each character c from the source string with its target index i from the indices list. Inside the loop, the character is stored directly at position i in the result list. Because the list was pre-sized, the assignment operation runs in constant time for each pair.

Conversion of the Container to the Final String

return "".join(result)

After all characters have been positioned, the list is transformed into a single string using the join method. This step concatenates the elements of result in order, producing the restored string that the method returns.

Edge Cases Handled by the Implementation

The algorithm gracefully manages several boundary conditions without additional checks.

When the input string is empty, len(s) evaluates to zero, resulting in an empty list result. The subsequent loop does not execute because zip yields no pairs, and the final join on an empty list returns an empty string. Thus, an empty input yields an empty output as expected.

If the indices list contains the identity permutation (i.e., each index matches its position), the loop writes each character back to its original slot. The final join reproduces the original string, confirming that the method correctly handles the no-reordering scenario.

When indices provides a reverse ordering, the loop still assigns each character to its new location, and the join produces the reversed string. This demonstrates that the method works for any bijective mapping of positions.

The code also tolerates duplicate characters in the source string because placement is driven solely by the index values, not by character uniqueness. Consequently, strings with repeated symbols are reconstructed accurately.

Performance Optimizations Observed

The implementation exhibits several deliberate choices that contribute to efficient execution.

Pre-allocating the result list avoids the overhead associated with repeatedly appending to a dynamic array. By knowing the exact size upfront, the algorithm sidesteps potential reallocations and copying that would occur with incremental growth.

Using zip to iterate over both s and indices in a single pass eliminates the need for separate indexing variables or multiple loops. This tight coupling reduces interpreter overhead and keeps the iteration count minimal-exactly the length of the input string.

Assigning characters directly into the list by index leverages Python’s O(1) list item assignment. No intermediate data structures are created during the placement phase, which conserves memory and speeds up the operation.

Finally, the join method is the idiomatic way to concatenate a sequence of strings in Python. It performs the concatenation in a single pass, allocating the final string only once. This is markedly faster than repeatedly using the + operator, which would generate intermediate strings and increase memory churn.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a row of empty boxes laid out on a table, and each box has a special number written on it. You also have a handful of colorful letter stickers that are currently all mixed up. Each sticker has a letter on the front and a secret number on the back that tells you exactly which box it belongs in.

To fix the mess, you pick up a sticker, look at the secret number on the back, and walk over to the box with that same number. You carefully place the sticker inside its matching home. You keep doing this for every single sticker you have until every box is filled with the right letter. Once all the boxes are tucked away in their correct spots, you look at them from left to right and read the letters to see the new word you have built.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 9 | μ = 8.56 | σ = 0.79

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++
leetcode.ca C++ Python Java JS Go Rust TS
Progiez C++ Python Java
github black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
FelixFan1122 Java
fsq C++
haoel C++
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
MacJim C++
muhammadfarhankt Go
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
FelixFan1122 Java
fsq C++
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
MacJim C++
muhammadfarhankt Go
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
34 links | 23 authors | 10 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

10 solutions   December 23, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality