String Code Replacement — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the String Code Replacement problem optimally.
O(N·K)O(T)Problem Description
Given a string transmission and a dictionary decodingMap where each key and its associated value are non‑empty strings, construct a new string by scanning transmission from left to right. At each index, identify all keys that match a prefix of the remaining substring. If no key matches, copy the current character to the result and move one position forward. If one or more keys match, select the longest matching key, append its mapped value to the result, and advance the scan by the length of that key. The inserted value is never examined again for further replacements (the process is non‑recursive). Return the final assembled string.
DSA Pattern Breakdown
DSA Pattern Breakdown
"String Code Replacement"
WHY DOES IT MATTER?
Prefix‑matching with longest‑match semantics appears in compilers (lexical analysis), URL routing, and protocol decoding; mastering it prevents exponential blow‑up when many patterns share prefixes.
OPTIMIZATION CHALLENGE
The key insight is to share common prefixes among dictionary keys, turning repeated character comparisons into a single walk through a Trie, which collapses O(M) checks per position into O(K).
REAL-WORLD CONNECTION
Think of a network packet inspector that replaces known protocol headers with human‑readable tags; the inspector must scan the byte stream once and substitute the longest known header to preserve meaning.
During an interview, build the Trie first, then write the scan loop; keep a pointer to the deepest terminal node while traversing so you can instantly emit the longest replacement without backtracking.
COMPLEXITY AT A GLANCE
O(N·K)O(T)Core Theory — Why This Approach?
The problem reduces to finding, at each position of the transmission, the longest dictionary key that matches the upcoming characters. A naïve solution would test every key at every index, leading to O(N·M·L) time where N is the transmission length, M the number of keys, and L the average key length—impractical for large inputs. The optimal paradigm builds a prefix tree (Trie) from all keys, enabling a single linear scan of the transmission while walking the Trie character‑by‑character to discover the longest match in O(N·K) where K is the maximum key length, often much smaller than M. This approach leverages the fact that overlapping prefixes are shared in the Trie, eliminating redundant comparisons and yielding linear‑time performance relative to the input size.
Interview Questions on This Problem
Q1How would you handle overlapping keys such as "ab" → "X" and "abc" → "Y" to ensure the longest match is chosen?
Insert all keys into a Trie and, while scanning the transmission, continue walking the Trie as long as characters match, recording the deepest node that marks the end of a key. After the walk stops, replace using the recorded longest key.
Q2Can you modify the solution to support dynamic updates to the decodingMap (add/remove keys) without rebuilding the entire structure?
Yes—because a Trie supports incremental insertion and deletion of keys. Adding a key is a simple path creation; removing a key clears the end‑of‑word flag and optionally prunes dead branches, keeping the overall structure intact.
Q3What alternative algorithm (besides a Trie) could solve this problem in O(N + totalKeyLength) and what are its trade‑offs?
Aho‑Corasick automaton can locate all pattern occurrences in a single pass, but it reports all matches, not just the longest prefix at each index. You would need extra logic to select the longest match, which adds complexity; however, it excels when you need to find matches anywhere, not just prefixes.
Examples
Input
transmission=\"ababc\", decodingMap={\"ab\":\"x\",\"abc\":\"y\"}Output
xy
Explanation: Start at index 0: the substrings "ab" and "abc" are examined. Only "ab" matches, so its value "x" is appended and the index moves to 2. At index 2 the remaining text is "abc"; both "ab" and "abc" match, but "abc" is longer, so "y" is appended and the scan jumps past the three characters. No characters remain, yielding "xy".
Input
transmission=\"aaaaa\", decodingMap={\"aa\":\"b\",\"a\":\"c\"}Output
bbc
Explanation: Index 0: "aa" (len 2) and "a" (len 1) match; the longer "aa" is chosen, appending "b" and moving to index 2. Index 2 repeats the same choice, appending another "b" and moving to index 4. At index 4 only "a" matches, so "c" is appended. The scan ends with the result "bbc".
Input
transmission=\"xyz\", decodingMap={\"xy\":\"p\",\"yz\":\"q\",\"x\":\"r\"}Output
pz
Explanation: At index 0, "xy" (len 2) and "x" (len 1) match; the longer "xy" is selected, adding "p" and advancing to index 2. Index 2 points to "z" which matches no key, so the character "z" is copied verbatim. The final string is "pz".
Input
transmission=\"ab\", decodingMap={\"a\":\"ab\",\"ab\":\"c\"}Output
c
Explanation: Both keys "a" and "ab" match at index 0, but "ab" is longer, so its value "c" is emitted and the scan jumps past the two original characters. The inserted "c" is not rescanned, so the output remains "c".
Constraints
- 1 <= transmission.length <= 10^5
- 1 <= decodingMap.size() <= 10^4
- All keys and values consist solely of lowercase English letters
- Sum of lengths of all keys does not exceed 10^5
Optimal Approach & Strategy
Construct a Trie of the keys and scan the transmission once, walking the Trie to find the longest matching key at each position.
Brute Force Approach
Check every dictionary key at every index of the transmission, picking the longest match or copying the character if none match.
Code Solutions
/**
* @param {string} transmission
* @param {Object<string, string>} decodingMap
* @return {string}
*/
function decodeTransmission(transmission, decodingMap) {
let result = "";
const n = transmission.length;
let i = 0;
while (i < n) {
let matched = false;
// Check for the longest match first
for (let len = n - i; len >= 1; --len) {
const prefix = transmission.substring(i, i + len);
if (decodingMap.hasOwnProperty(prefix)) {
result += decodingMap[prefix];
i += len;
matched = true;
break;
}
}
if (!matched) {
result += transmission[i];
i++;
}
}
return result;
}
// Example usage
const transmission = "ababc";
const decodingMap = { "ab": "x", "abc": "y" };
console.log(decodeTransmission(transmission, decodingMap));#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
string decodeTransmission(string transmission, unordered_map<string, string> decodingMap) {
string result = "";
int n = transmission.length();
int i = 0;
while (i < n) {
bool matched = false;
// Check for the longest match first
for (int len = n - i; len >= 1; --len) {
string prefix = transmission.substr(i, len);
if (decodingMap.find(prefix) != decodingMap.end()) {
result += decodingMap[prefix];
i += len;
matched = true;
break;
}
}
if (!matched) {
result += transmission[i];
i++;
}
}
return result;
}
int main() {
// Example usage
string transmission = "ababc";
unordered_map<string, string> decodingMap = {{"ab", "x"}, {"abc", "y"}};
cout << decodeTransmission(transmission, decodingMap) << endl;
return 0;
}import java.util.HashMap;
import java.util.Map;
public class Main {
public static String decodeTransmission(String transmission, Map<String, String> decodingMap) {
StringBuilder result = new StringBuilder();
int n = transmission.length();
int i = 0;
while (i < n) {
boolean matched = false;
// Check for the longest match first
for (int len = n - i; len >= 1; --len) {
String prefix = transmission.substring(i, i + len);
if (decodingMap.containsKey(prefix)) {
result.append(decodingMap.get(prefix));
i += len;
matched = true;
break;
}
}
if (!matched) {
result.append(transmission.charAt(i));
i++;
}
}
return result.toString();
}
public static void main(String[] args) {
// Example usage
String transmission = "ababc";
Map<String, String> decodingMap = new HashMap<>();
decodingMap.put("ab", "x");
decodingMap.put("abc", "y");
System.out.println(decodeTransmission(transmission, decodingMap));
}
}def decode_transmission(transmission: str, decoding_map: dict) -> str:
"""
Decodes the transmission string using the provided decoding map.
Args:
transmission: The input string to decode.
decoding_map: A dictionary mapping keys to replacement values.
Returns:
The decoded string.
"""
result = []
n = len(transmission)
i = 0
while i < n:
matched = False
# Check for the longest match first
for length in range(n - i, 0, -1):
prefix = transmission[i:i + length]
if prefix in decoding_map:
result.append(decoding_map[prefix])
i += length
matched = True
break
if not matched:
result.append(transmission[i])
i += 1
return "".join(result)
# Example usage
if __name__ == "__main__":
transmission = "ababc"
decoding_map = {"ab": "x", "abc": "y"}
print(decode_transmission(transmission, decoding_map))/**
* @param {string} transmission
* @param {Object<string, string>} decodingMap
* @return {string}
*/
function decodeTransmission(transmission, decodingMap) {
let result = "";
const n = transmission.length;
let i = 0;
while (i < n) {
let matched = false;
// Check for the longest match first
for (let len = n - i; len >= 1; --len) {
const prefix = transmission.substring(i, i + len);
if (decodingMap.hasOwnProperty(prefix)) {
result += decodingMap[prefix];
i += len;
matched = true;
break;
}
}
if (!matched) {
result += transmission[i];
i++;
}
}
return result;
}
// Example usage
const transmission = "ababc";
const decodingMap = { "ab": "x", "abc": "y" };
console.log(decodeTransmission(transmission, decodingMap));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.