String Reconstruction from Character Counts — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the String Reconstruction from Character Counts problem optimally.
O(totalLength)O(totalLength)Problem Description
Given a list of character counts, where each character count is a pair of a character and its count, reconstruct the original string if possible, otherwise return an empty string. The counts are cumulative, meaning each character is added to the result the specified number of times.
DSA Pattern Breakdown
DSA Pattern Breakdown
"String Reconstruction from Character Counts"
WHY DOES IT MATTER?
Run‑length decoding is a foundational pattern for any scenario where data is stored or transmitted in compressed form; mastering it enables engineers to efficiently reconstruct original data without unnecessary overhead.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the problem is a direct RLE decode, allowing a single pass with a mutable buffer and eliminating any need for sorting, hashing, or repeated scans.
REAL-WORLD CONNECTION
Think of a log aggregation service that receives batched counts of error codes; reconstructing the exact sequence of errors from these batches mirrors expanding character counts into a full string.
During an interview, allocate a few seconds to confirm the input order matters; then immediately reach for a StringBuilder (or equivalent) and a simple for‑loop—this signals both correctness and performance awareness.
COMPLEXITY AT A GLANCE
O(totalLength)O(totalLength)Core Theory — Why This Approach?
The problem reduces to a linear reconstruction of a string from its frequency map. Each pair (c, f) indicates that character c must appear exactly f times in the final output, preserving the order of the pairs as they appear in the input list. A naive solution might attempt to sort or search for each character repeatedly, leading to O(n × k) time where n is the number of distinct pairs and k is the total length of the resulting string, which quickly becomes infeasible for large inputs (e.g., when the sum of counts reaches 10^7). The optimal paradigm leverages the fact that string concatenation can be performed in O(1) amortized time per character when using a mutable buffer (such as StringBuilder in Java or list of characters in Python) and that the reconstruction is a simple linear scan over the input pairs, appending each character count times. This yields a single-pass O(totalLength) algorithm with O(totalLength) auxiliary space for the output buffer, which is optimal because any algorithm must at least write each character once.
The underlying theory aligns with the concept of "frequency‑based reconstruction" common in compression and decoding tasks. By treating the input as a run‑length encoded (RLE) representation, we can directly decode it without any additional data structures beyond the output buffer. This avoids the overhead of hash maps or sorting, which would add unnecessary logarithmic factors. The key insight is that the order of characters in the original string is fully determined by the order of the count pairs, so we can simply expand each run in place.
Interview Questions on This Problem
Q1How would you modify the solution if the input list could contain duplicate characters with separate counts, and the final string must preserve the original order of appearance?
Simply iterate over the list as given; for each (c, f) pair, append c f times to the result. Duplicate characters are naturally handled because each occurrence is expanded in the order they appear, preserving the required sequence.
Q2What changes are needed if the output string must be lexicographically sorted after reconstruction?
First reconstruct the string using the linear expansion, then sort the resulting characters using a counting sort (since the alphabet size is bounded) to achieve O(totalLength + σ) time, where σ is the size of the character set.
Q3In a distributed system where each node processes a subset of the count pairs, how can you combine partial results to obtain the final string efficiently?
Each node expands its assigned pairs locally into a substring; the coordinator then concatenates the substrings in the original global order of the pairs, which can be done in O(numberOfNodes) communication steps and O(totalLength) total time.
Examples
Input
[['a', 1], ['b', 2]]
Output
Explanation: Step-by-step: Given the input [['a', 1], ['b', 2]], we iterate over the character counts. We add 'a' once to the result because its count is 1. Then, we add 'b' twice to the result because its count is 2. Therefore, the output is 'ab'.
Input
[['a', 3], ['b', 2], ['c', 1]]
Output
Explanation: Step-by-step: Given the input [['a', 3], ['b', 2], ['c', 1]], we iterate over the character counts. We add 'a' three times to the result because its count is 3. Then, we add 'b' twice to the result because its count is 2. Finally, we add 'c' once to the result because its count is 1. Therefore, the output is 'abcc'.
Constraints
- The length of the input list is at most 26, representing the 26 English letters.
- The count of each character is a non-negative integer.
- The total count of all characters is at most 10^5.
Optimal Approach & Strategy
Use a StringBuilder (or character array) and a single loop: for each (c, f) append c f times. This runs in linear time relative to the final string length and uses only the output buffer as extra space.
Brute Force Approach
A naive method would iterate over the list and for each pair, repeatedly search the result string to insert the character, leading to O(n × k) time. It also might rebuild the string on every insertion, causing huge overhead.
Code Solutions
function reconstruct(counts) {
let result = '';
for (const [ch, cnt] of counts) {
if (typeof cnt !== 'number' || cnt < 0) return '';
result += ch.repeat(cnt);
}
return result;
}
// Example usage:
const input = [['a', 1], ['b', 2]];
console.log(reconstruct(input)); // prints "abb"#include <bits/stdc++.h>
using namespace std;
string reconstruct(const vector<pair<char, int>>& counts) {
string result;
for (const auto& p : counts) {
char ch = p.first;
int cnt = p.second;
if (cnt < 0) return ""; // invalid count
result.append(cnt, ch);
}
return result;
}
int main() {
vector<pair<char, int>> input = {{'a', 1}, {'b', 2}};
cout << reconstruct(input) << endl; // prints "abb"
return 0;
}import java.util.*;
public class StringReconstruction {
public static String reconstruct(List<Pair<Character, Integer>> counts) {
StringBuilder sb = new StringBuilder();
for (Pair<Character, Integer> p : counts) {
char ch = p.first;
int cnt = p.second;
if (cnt < 0) return ""; // invalid count
for (int i = 0; i < cnt; i++) {
sb.append(ch);
}
}
return sb.toString();
}
public static class Pair<F, S> {
public final F first;
public final S second;
public Pair(F first, S second) {
this.first = first;
this.second = second;
}
}
public static void main(String[] args) {
List<Pair<Character, Integer>> input = new ArrayList<>();
input.add(new Pair<>('a', 1));
input.add(new Pair<>('b', 2));
System.out.println(reconstruct(input)); // prints "abb"
}
}def reconstruct(counts):
"""Reconstruct the original string from character counts.
Returns an empty string if any count is negative or not an integer.
"""
result = []
for ch, cnt in counts:
if not isinstance(cnt, int) or cnt < 0:
return ""
result.append(ch * cnt)
return "".join(result)
# Example usage:
if __name__ == "__main__":
input_data = [['a', 1], ['b', 2]]
print(reconstruct(input_data)) # prints "abb"function reconstruct(counts) {
let result = '';
for (const [ch, cnt] of counts) {
if (typeof cnt !== 'number' || cnt < 0) return '';
result += ch.repeat(cnt);
}
return result;
}
// Example usage:
const input = [['a', 1], ['b', 2]];
console.log(reconstruct(input)); // prints "abb"Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.