Reverse Character Groups — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Reverse Character Groups problem optimally.
O(n)O(1)Problem Description
Given an alphanumeric string S, transform it according to the following rule: if |S| is a multiple of three, split S into consecutive blocks of three characters and reverse the characters inside each block; otherwise, reverse the whole string. Return the resulting string.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Reverse Character Groups"
WHY DOES IT MATTER?
Block‑wise reversal is a recurring pattern in data‑encoding, checksum calculations, and cryptographic primitives where fixed‑size chunks are processed independently, so mastering it helps solve many low‑level string manipulation tasks efficiently.
OPTIMIZATION CHALLENGE
The key insight is recognizing that both required operations—per‑block reversal and full reversal—are reversible via simple two‑pointer swaps, allowing a single linear pass without auxiliary buffers, thus collapsing what appears to be two distinct cases into one unified O(n) algorithm.
REAL-WORLD CONNECTION
Think of network packet processing: routers often split a payload into fixed‑size frames, apply transformations (e.g., endian swaps) per frame, and forward them. If the payload size isn’t a multiple of the frame size, the entire payload may be re‑ordered or padded, mirroring the conditional whole‑string reversal.
During the interview, write the solution as a mutable array, handle the length‑mod‑3 check first, then either loop with step‑3 swaps or fall back to a classic two‑pointer reverse; this demonstrates both correctness and awareness of constant‑space optimization.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem boils down to a conditional string transformation that can be expressed as a linear scan. If the length of the input string is divisible by three, the string can be partitioned into fixed‑size blocks of three characters; each block is then reversed independently. This is a classic example of a block‑wise operation, which can be performed in O(n) time by iterating over the string with a step of three and swapping the first and third characters of each block. When the length is not a multiple of three, the whole string must be reversed, which is also a linear‑time operation using two‑pointer swapping. Naïve solutions that rebuild substrings repeatedly (e.g., using repeated concatenation or slicing inside loops) incur O(n²) time due to the immutable nature of strings in many languages, making them unsuitable for large inputs (up to 10⁶ characters). The optimal paradigm leverages in‑place character array manipulation or a single pass construction, guaranteeing linear time and constant auxiliary space, which is essential for scalability and for meeting strict interview time constraints.
Interview Questions on This Problem
Q1How would you handle the transformation if the block size were a variable k instead of a fixed 3?
Treat k as a parameter; if |S| % k == 0, iterate i from 0 to n‑1 in steps of k and reverse each k‑length segment in place (swap i+j with i+k‑1‑j for j<k/2). Otherwise, reverse the entire string. The algorithm remains O(n) time and O(1) extra space.
Q2Why is it preferable to work on a mutable character array rather than repeatedly using string concatenation in languages like Java or Python?
Strings are immutable, so each concatenation creates a new string and copies all characters, leading to O(n²) total work for n characters. A mutable array (char[] or list) allows constant‑time swaps and a single final conversion, preserving the linear O(n) runtime.
Q3Can this problem be solved using a stack or queue, and what would be the trade‑offs?
A stack can reverse the whole string by pushing all characters and popping them, which is O(n) time but O(n) extra space. For the block‑wise case, a stack per block adds overhead; using in‑place swaps is more space‑efficient (O(1)) and simpler, making it the preferred solution in interviews.
Examples
Input
a1b2c3d4e5
Output
5e4d3c2b1a
Explanation: The length of the input is 10, which is not divisible by 3, so the entire string is reversed.
Input
abc123def
Output
cba321fed
Explanation: Length 9 is divisible by 3. The blocks are "abc","123","def". Reversing each yields "cba","321","fed"; concatenating gives "cba321fed".
Input
XyZ
Output
ZyX
Explanation: Length 3 is a multiple of 3, so the single block "XyZ" is reversed to "ZyX".
Constraints
- 1 <= |S| <= 100000
- S consists only of ASCII letters (a-z, A-Z) and digits (0-9)
Optimal Approach & Strategy
Convert the string to a mutable array, perform in‑place swaps for each three‑character block or a full two‑pointer reverse, then rebuild the string, achieving O(n) time and O(1) extra space.
Brute Force Approach
Repeatedly slice the string into substrings, reverse each slice with built‑in functions, and concatenate the results, which leads to O(n²) time due to repeated copying.
Code Solutions
/**
* @param {string} s
* @return {string}
*/
function reverseCharacterGroups(s) {
const n = s.length;
if (n % 3 === 0) {
let result = '';
for (let i = 0; i < n; i += 3) {
const block = s.substring(i, i + 3);
result += block.split('').reverse().join('');
}
return result;
} else {
return s.split('').reverse().join('');
}
}
// 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(reverseCharacterGroups(s));
rl.close();
});#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string reverseCharacterGroups(string s) {
int n = s.length();
if (n % 3 == 0) {
for (int i = 0; i < n; i += 3) {
reverse(s.begin() + i, s.begin() + i + 3);
}
} else {
reverse(s.begin(), s.end());
}
return s;
}
int main() {
string s;
cin >> s;
cout << reverseCharacterGroups(s) << endl;
return 0;
}import java.util.Scanner;
public class Main {
public static String reverseCharacterGroups(String s) {
int n = s.length();
if (n % 3 == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i += 3) {
String block = s.substring(i, i + 3);
sb.append(new StringBuilder(block).reverse());
}
return sb.toString();
} else {
return new StringBuilder(s).reverse().toString();
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(reverseCharacterGroups(s));
scanner.close();
}
}def reverse_character_groups(s: str) -> str:
n = len(s)
if n % 3 == 0:
result = []
for i in range(0, n, 3):
block = s[i:i+3]
result.append(block[::-1])
return ''.join(result)
else:
return s[::-1]
if __name__ == "__main__":
s = input().strip()
print(reverse_character_groups(s))/**
* @param {string} s
* @return {string}
*/
function reverseCharacterGroups(s) {
const n = s.length;
if (n % 3 === 0) {
let result = '';
for (let i = 0; i < n; i += 3) {
const block = s.substring(i, i + 3);
result += block.split('').reverse().join('');
}
return result;
} else {
return s.split('').reverse().join('');
}
}
// 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(reverseCharacterGroups(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.