Galactic Transmission Encoding — Problem Statement & Solution Guide
Problem Description
Given a string S composed exclusively of lowercase English letters, where 97 ≤ |S| ≤ 6787, produce its run‑length encoding. For each maximal block of identical characters, output the character followed by the block length if the length exceeds one; otherwise output only the character. Concatenate the results in order to form the encoded string and return it.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Transmission Encoding"
WHY DOES IT MATTER?
Run‑length encoding teaches candidates how to collapse repetitive data efficiently, a pattern that recurs in compression, data deduplication, and even in state‑machine optimizations where consecutive identical events can be merged.
OPTIMIZATION CHALLENGE
The insight is to avoid re‑scanning already processed characters; by advancing a single pointer and emitting output only when the run ends, we achieve linear time and eliminate the need for auxiliary arrays or nested loops.
REAL-WORLD CONNECTION
Think of a network packet aggregator that batches identical sensor readings before transmission to reduce bandwidth—RLE is the software analogue of that batching process.
During an interview, implement the solution with a mutable string builder and a simple while loop; remember to handle the final run after the loop exits—this off‑by‑one bug trips many candidates.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
Run‑length encoding (RLE) is a classic compression technique that replaces consecutive identical symbols with a single instance of the symbol followed by the count of repetitions. The optimal algorithm scans the input string once, maintaining a pointer to the current character and a counter for its run length; when the next character differs, it appends the character and, if the count>1, the count itself to the result. This linear‑time, constant‑extra‑space approach leverages the fact that the output size is bounded by O(n) and no back‑tracking or nested loops are required. Naïve solutions that, for each character, search forward for the end of its block or repeatedly concatenate strings using immutable operations incur O(n²) time due to repeated scanning or copying, which becomes prohibitive for the maximum length of 6,787 characters.
The optimal paradigm falls under the “two‑pointer / sliding window” family: one pointer iterates through the string while the other marks the start of the current run. By updating the result in a mutable buffer (e.g., StringBuilder in Java or list of chars in Python) we avoid the overhead of immutable concatenation, guaranteeing O(n) time and O(1) auxiliary space (excluding the output). This pattern is a staple for any problem that requires grouping or compressing consecutive elements, making it a must‑know for interviewers assessing algorithmic efficiency.
Interview Questions on This Problem
Q1How would you modify the RLE algorithm to handle Unicode characters and potentially very large counts that exceed 32‑bit integer limits?
Use a language‑agnostic approach: store the count in a 64‑bit integer (or arbitrary‑precision type) and treat the input as a sequence of Unicode code points rather than bytes; iterate using a Unicode‑aware iterator and append the count using its decimal representation, ensuring the buffer can grow dynamically.
Q2At a fintech firm, you need to compress transaction logs that contain repeated status codes. What trade‑offs would you consider when choosing run‑length encoding versus a dictionary‑based compression like Huffman?
RLE excels when repetitions are long and predictable, offering O(n) time and minimal CPU overhead, but it can inflate data with many short runs. Huffman provides better compression for varied patterns at the cost of building a frequency table and tree, increasing time and memory. The choice hinges on log characteristics, latency constraints, and storage cost.
Q3A high‑growth startup wants to stream encoded messages over a WebSocket with minimal latency. How can you implement RLE in a streaming fashion without waiting for the entire message?
Maintain state across chunks: keep the last character and its current count. For each incoming chunk, continue counting runs, emitting encoded segments as soon as a character change is detected or the chunk ends, flushing the final run when the stream closes. This yields constant‑space, low‑latency processing.
Examples
Input
aaabccccde
Output
a3bc4de
Explanation: The first three characters are 'a' → count 3 → "a3". Next is a single 'b' → "b". Then four 'c's → "c4". 'd' and 'e' appear once each → "d" and "e". Combined: "a3bc4de".
Input
xyz
Output
xyz
Explanation: All characters appear singly, so each is written unchanged, yielding "xyz".
Input
mmmmnnnnnnppqqqqqqqrrrrrrrrr
Output
m4n6p2q7r9
Explanation: 'm' repeats 4 → "m4"; 'n' repeats 6 → "n6"; 'p' repeats 2 → "p2"; 'q' repeats 7 → "q7"; 'r' repeats 9 → "r9". Concatenated result is "m4n6p2q7r9".
Constraints
- 97 ≤ |S| ≤ 6787
- S contains only characters 'a' through 'z'
Optimal Approach & Strategy
Use a single pass with a mutable buffer, increment a counter for each run, and append the character and count (if >1) when the run ends.
Brute Force Approach
For each character, repeatedly scan forward to count its consecutive duplicates and concatenate the result using immutable strings, leading to repeated copying.
Verified Code Solutions
/**
* @param {string} s - The input string consisting of lowercase English letters.
* @return {string} - The run-length encoded string.
*/
function encodeString(s) {
if (!s || s.length === 0) return "";
let result = "";
let i = 0;
const n = s.length;
while (i < n) {
const currentChar = s[i];
let count = 1;
while (i + count < n && s[i + count] === currentChar) {
count++;
}
result += currentChar;
if (count > 1) {
result += count;
}
i += count;
}
return result;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
rl.on('line', (line) => {
const s = line.trim();
console.log(encodeString(s));
rl.close();
});#include <iostream>
#include <string>
using namespace std;
string encodeString(const string& s) {
if (s.empty()) return "";
string result;
int n = s.length();
int i = 0;
while (i < n) {
char currentChar = s[i];
int count = 1;
while (i + count < n && s[i + count] == currentChar) {
count++;
}
result += currentChar;
if (count > 1) {
result += to_string(count);
}
i += count;
}
return result;
}
int main() {
string s;
cin >> s;
cout << encodeString(s) << endl;
return 0;
}import java.util.Scanner;
public class Main {
/**
* Encodes a string using run-length encoding.
*
* For each maximal block of identical characters, output the character followed by the block length if the length exceeds one; otherwise output only the character.
*
* @param s The input string consisting of lowercase English letters.
* @return The run-length encoded string.
*/
public static String encodeString(String s) {
if (s == null || s.isEmpty()) return "";
StringBuilder result = new StringBuilder();
int n = s.length();
int i = 0;
while (i < n) {
char currentChar = s.charAt(i);
int count = 1;
while (i + count < n && s.charAt(i + count) == currentChar) {
count++;
}
result.append(currentChar);
if (count > 1) {
result.append(count);
}
i += count;
}
return result.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(encodeString(s));
scanner.close();
}
}def encode_string(s: str) -> str:
"""
Encodes a string using run-length encoding.
For each maximal block of identical characters, output the character followed by the block length if the length exceeds one; otherwise output only the character.
Args:
s (str): The input string consisting of lowercase English letters.
Returns:
str: The run-length encoded string.
"""
if not s:
return ""
result = []
n = len(s)
i = 0
while i < n:
current_char = s[i]
count = 1
while i + count < n and s[i + count] == current_char:
count += 1
result.append(current_char)
if count > 1:
result.append(str(count))
i += count
return "".join(result)
if __name__ == "__main__":
s = input().strip()
print(encode_string(s))/**
* @param {string} s - The input string consisting of lowercase English letters.
* @return {string} - The run-length encoded string.
*/
function encodeString(s) {
if (!s || s.length === 0) return "";
let result = "";
let i = 0;
const n = s.length;
while (i < n) {
const currentChar = s[i];
let count = 1;
while (i + count < n && s[i + count] === currentChar) {
count++;
}
result += currentChar;
if (count > 1) {
result += count;
}
i += count;
}
return result;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
rl.on('line', (line) => {
const s = line.trim();
console.log(encodeString(s));
rl.close();
});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.