Consecutive Character Encoder — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Consecutive Character Encoder problem optimally.
O(n)O(1)Problem Description
Given a lowercase English string s, produce its encoded form according to the following rules. Scan s from left to right and group consecutive identical characters. For each group:
- If the group length is 1, output the character alone.
- If the group length is 2, output the two characters unchanged.
- If the group length is ≥ 3, output the character followed by the decimal representation of the group length.
The resulting concatenation is the answer. Implement a function that receives s and returns the encoded string.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Consecutive Character Encoder"
WHY DOES IT MATTER?
Run‑length style compression appears in many low‑bandwidth protocols and log‑storage systems; recognizing when to compress versus when to keep data verbatim saves both space and processing time.
OPTIMIZATION CHALLENGE
The key insight is that you never need to look back once a run is closed; a single forward pointer plus a counter suffices, eliminating the need for nested loops or auxiliary arrays.
REAL-WORLD CONNECTION
Think of a network packet aggregator that batches identical requests: sending "REQ,REQ,REQ" as "REQx3" reduces payload, similar to how the encoder collapses repeated characters.
During an interview, write the loop that increments the count, then immediately handle the three cases (1,2,>=3) in a small helper function – this keeps the main flow clean and avoids off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic run‑length encoding variant where we must compress only runs of three or more identical characters while preserving runs of length one or two. A naive solution would repeatedly search for the next change in character using nested loops, leading to O(n^2) time on pathological inputs like "aaaaaaaa..." because each inner scan restarts from the current position. The optimal paradigm is a single linear scan that maintains a count of the current run, emitting the appropriate token as soon as the character changes or the string ends. This leverages the fact that each character is visited exactly once, guaranteeing O(n) time and O(1) auxiliary space, which scales to the maximum input size constraints typical in coding interviews.
Interview Questions on This Problem
Q1How would you modify the encoder to handle uppercase letters and digits while preserving the same compression rules?
Treat the input as a generic character stream; the algorithm remains unchanged because it only relies on equality comparison. Ensure the output format (character followed by count) can represent any ASCII character, possibly escaping special symbols if required.
Q2If the encoded string must be decoded back to the original, what additional information (if any) do you need to store?
No extra information is needed; the decoder can parse a character followed by digits as a run length (>=3) and treat solitary characters or two consecutive identical characters as literal runs. Care must be taken to differentiate a digit that is part of a run length from a digit that is itself a character in the original string.
Q3Can you extend the solution to work in a streaming context where the input arrives character by character?
Yes. Keep a buffer for the current run and its count. When a new character differs from the buffered one, flush the encoded token according to the count rules and reset the buffer. At stream end, flush the final run. This maintains O(1) memory per stream chunk.
Examples
Input
aabcccdeeefffgg
Output
aab c3 d e3 f3 gg
Explanation: The input is split into groups: "aa" (length 2 → kept as "aa"), "b" (1 → "b"), "ccc" (3 → "c3"), "d" (1 → "d"), "eee" (3 → "e3"), "fff" (3 → "f3"), "gg" (2 → "gg"). Concatenating yields "aab c3 d e3 f3 gg" which, without spaces, is "aabc3de3f3gg".
Input
zzzyxxyyyy
Output
z3 xy y4
Explanation: Groups: "zzz" → "z3", "y" → "y", "xx" → "xx" (length 2, unchanged), "yyyy" → "y4". Concatenating gives "z3yxx y4" → "z3yxx y4" without spaces: "z3yxx y4" (final string "z3yxx y4").
Input
pqrstu
Output
pqrstu
Explanation: All characters appear singly, so each group length is 1 and the output is identical to the input.
Constraints
- 1 <= s.length <= 10^5
- s consists only of lowercase English letters ('a'‑'z')
- The algorithm must run in O(|s|) time and O(1) additional space besides the output
Optimal Approach & Strategy
Maintain a single pass with a running count; when the character changes, emit the token based on the count and reset the counter, achieving linear time and O(1) extra space.
Brute Force Approach
Repeatedly search for the next different character using a nested loop, recomputing run lengths each time, which can degrade to quadratic time on long uniform strings.
Code Solutions
function encode(s) {
let res = '';
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
const len = j - i;
if (len === 1) {
res += s[i];
} else if (len === 2) {
res += s[i] + s[i];
} else {
res += s[i] + len;
}
i = j;
}
return res;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) {
console.log(encode(input));
}#include <bits/stdc++.h>
using namespace std;
string encode(const string& s) {
string res;
int n = s.size();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s[j] == s[i]) ++j;
int len = j - i;
if (len == 1) {
res.push_back(s[i]);
} else if (len == 2) {
res.push_back(s[i]);
res.push_back(s[i]);
} else {
res.push_back(s[i]);
res += to_string(len);
}
i = j;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
if(!(cin>>s)) return 0;
cout << encode(s);
return 0;
}import java.io.*;
public class Main {
static String encode(String s) {
StringBuilder sb = new StringBuilder();
int n = s.length();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) j++;
int len = j - i;
if (len == 1) {
sb.append(s.charAt(i));
} else if (len == 2) {
sb.append(s.charAt(i)).append(s.charAt(i));
} else {
sb.append(s.charAt(i)).append(len);
}
i = j;
}
return sb.toString();
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
if (s != null) {
System.out.print(encode(s));
}
}
}def encode(s: str) -> str:
res = []
i = 0
n = len(s)
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
length = j - i
if length == 1:
res.append(s[i])
elif length == 2:
res.append(s[i] * 2)
else:
res.append(s[i] + str(length))
i = j
return ''.join(res)
def main():
import sys
data = sys.stdin.read().strip()
if data:
print(encode(data))
if __name__ == "__main__":
main()function encode(s) {
let res = '';
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
const len = j - i;
if (len === 1) {
res += s[i];
} else if (len === 2) {
res += s[i] + s[i];
} else {
res += s[i] + len;
}
i = j;
}
return res;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) {
console.log(encode(input));
}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.