String Reconstruction from Character Counts — Problem Statement & Solution Guide
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.
Examples
Input
[['a', 1], ['b', 2]]
Output
ab
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
abcc
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
A more efficient approach is to use a single loop to iterate over the sorted character counts and append each character to the result string the specified number of times, resulting in a time complexity of O(n).
Brute Force Approach
One possible brute-force approach is to use a nested loop structure to generate all possible permutations of the characters and then check if the permutation matches the given character counts. However, this approach is inefficient and has a time complexity of O(n!).
Verified Code Solutions
function reconstructString(charCounts) {
let result = '';
for (let i = 0; i < charCounts.length; i++) {
let char = charCounts[i][0];
let count = charCounts[i][1];
result += char.repeat(count);
}
return result;
}class Solution {
public String reconstructString(char[][] charCounts) {
StringBuilder result = new StringBuilder();
for (char[] charCount : charCounts) {
char c = charCount[0];
int count = charCount[1];
for (int i = 0; i < count; i++) {
result.append(c);
}
}
return result.toString();
}
}def reconstruct_string(char_counts):
result = ''
for char, count in char_counts:
result += char * count
return resultfunction reconstructString(charCounts) {
let result = '';
for (let i = 0; i < charCounts.length; i++) {
let char = charCounts[i][0];
let count = charCounts[i][1];
result += char.repeat(count);
}
return result;
}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.