Galactic Transmission Optimization — Problem Statement & Solution Guide
Problem Description
Given a string S representing a transmission, compute the occurrence count of each distinct character. Produce a new string that lists all characters of S sorted primarily by decreasing frequency and secondarily by increasing ASCII code for ties. Each character must appear in the result exactly as many times as it appears in the original string. The input contains only printable ASCII characters.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Transmission Optimization"
WHY DOES IT MATTER?
Frequency‑based ordering appears in compression (e.g., Huffman coding), load‑balancing logs, and UI ranking where the most common items must be highlighted first; mastering this pattern teaches you to separate counting from ordering for optimal performance.
OPTIMIZATION CHALLENGE
The key insight is that the alphabet size (printable ASCII) is constant, so you can replace a generic O(N log N) sort with a linear‑time bucket or counting sort, turning the dominant factor from N log N to N.
REAL-WORLD CONNECTION
Think of a CDN that records request counts per asset; to decide cache eviction it sorts assets by request frequency (high to low) and then by URL lexical order for ties—exactly the same two‑key sort as this problem.
During an interview, first build the frequency table, then write a comparator that checks count first and ASCII second; if you’re nervous about sorting 128 items, just iterate frequencies from max down to 1 and output characters accordingly.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem reduces to counting character frequencies and then ordering the characters by a two‑key sort: descending frequency and ascending ASCII for ties. A frequency array (size 128 for printable ASCII) can be populated in a single linear scan, which gives O(N) time where N is the length of S. Once the counts are known, we need to emit each character exactly count times in the required order; this can be achieved by sorting the 128 possible characters using a custom comparator or by bucket‑sorting frequencies because the range of possible frequencies is bounded by N. Naïve solutions that recompute frequencies for each character or that repeatedly search for the maximum frequency lead to O(N^2) behavior on large strings, which quickly exceeds time limits. The optimal paradigm combines counting (a classic use‑case of the counting sort technique) with a stable ordering rule, yielding linear‑time performance and constant extra space for the frequency table.
Interview Questions on This Problem
Q1How would you modify the solution if the input could contain Unicode characters beyond ASCII?
Use a hash map (e.g., unordered_map<char32_t,int>) to store frequencies instead of a fixed‑size array, then collect the distinct keys and sort them with the same two‑key comparator; time remains O(N log U) where U is the number of unique Unicode code points present.
Q2Why is a counting‑sort style approach preferable to using std::sort on the original string?
Sorting the whole string would be O(N log N) and would also rearrange characters before we know their frequencies; counting sort leverages the small, fixed alphabet size to achieve O(N) time and O(1) extra space.
Q3In a distributed system that streams characters from many sources, how could you maintain the global ordering efficiently?
Each node can maintain a local frequency map; a central aggregator merges these maps by summing counts (O(K) where K is distinct characters) and then applies the same two‑key ordering, avoiding the need to transmit the entire raw stream.
Examples
Input
aabbc
Output
aabbc
Explanation: Frequencies – a:2, b:2, c:1. The highest frequency is 2. For the tie between a and b, ASCII('a')<ASCII('b'), so a precedes b. Append characters by their counts: a twice, b twice, then c once → aabbc.
Input
zzxy
Output
zzxy
Explanation: Frequencies – z:2, x:1, y:1. z has the greatest count, so it comes first. x and y share count 1; ASCII('x')<ASCII('y'), therefore x precedes y. Result: z twice, then x, then y → zzxy.
Input
bbaaccc
Output
cccaabb
Explanation: Frequencies – c:3, a:2, b:2. c has the highest count, placed first. a and b both have count 2; ASCII('a')<ASCII('b'), so a comes before b. Assemble: c three times, a twice, b twice → cccaabb.
Constraints
- 1 <= |S| <= 100000
- S contains only printable ASCII characters (code 32 to 126)
- The algorithm should run in O(|S| log K) time, where K is the number of distinct characters
- Memory usage must be O(K) besides the input string
Optimal Approach & Strategy
Build a fixed‑size frequency array in O(N) then sort the 128 characters with a custom comparator or bucket‑sort by frequency, yielding O(N) overall.
Brute Force Approach
Repeatedly find the most frequent remaining character by scanning the whole string each time, leading to O(N^2) time.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').replace(/\r?\n$/,'');
function optimizeTransmission(s){
const cnt = new Array(128).fill(0);
for(let i=0;i<s.length;i++) cnt[s.charCodeAt(i)]++;
const arr=[];
for(let i=0;i<128;i++) if(cnt[i]) arr.push({ch:String.fromCharCode(i),c:cnt[i]});
arr.sort((a,b)=>{
if(a.c!==b.c) return b.c-a.c; // decreasing freq
return a.ch.charCodeAt(0)-b.ch.charCodeAt(0); // increasing ASCII
});
let res='';
for(const o of arr) res+=o.ch.repeat(o.c);
return res;
}
console.log(optimizeTransmission(input));#include <bits/stdc++.h>
using namespace std;
string optimizeTransmission(const string &S){
const int MAXC=128;
int cnt[MAXC] = {0};
for(unsigned char ch: S) cnt[ch]++;
vector<pair<char,int>> v;
for(int i=0;i<MAXC;i++) if(cnt[i]) v.emplace_back((char)i,cnt[i]);
sort(v.begin(),v.end(),[](const auto &a,const auto &b){
if(a.second!=b.second) return a.second>b.second; // decreasing freq
return a.first<b.first; // increasing ASCII
});
string res; res.reserve(S.size());
for(auto &p: v) res.append(p.second,p.first);
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S; getline(cin,S);
cout<<optimizeTransmission(S);
return 0;
}import java.io.*;
import java.util.*;
public class Main{
static String optimizeTransmission(String s){
int[] cnt=new int[128];
for(int i=0;i<s.length();i++) cnt[s.charAt(i)]++;
List<int[]> list=new ArrayList<>();
for(int i=0;i<128;i++) if(cnt[i]>0) list.add(new int[]{i,cnt[i]});
list.sort((a,b)->{
if(a[1]!=b[1]) return b[1]-a[1]; // decreasing freq
return a[0]-b[0]; // increasing ASCII
});
StringBuilder sb=new StringBuilder(s.length());
for(int[] p:list){
for(int i=0;i<p[1];i++) sb.append((char)p[0]);
}
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) s="";
System.out.print(optimizeTransmission(s));
}
}import sys
from collections import Counter
def optimize_transmission(s):
cnt=Counter(s)
# sort by (-freq, ascii)
items=sorted(cnt.items(),key=lambda kv:(-kv[1],ord(kv[0])))
return ''.join(ch*freq for ch,freq in items)
if __name__=='__main__':
s=sys.stdin.read().rstrip('\n')
print(optimize_transmission(s))const fs = require('fs');
const input = fs.readFileSync(0,'utf8').replace(/\r?\n$/,'');
function optimizeTransmission(s){
const cnt = new Array(128).fill(0);
for(let i=0;i<s.length;i++) cnt[s.charCodeAt(i)]++;
const arr=[];
for(let i=0;i<128;i++) if(cnt[i]) arr.push({ch:String.fromCharCode(i),c:cnt[i]});
arr.sort((a,b)=>{
if(a.c!==b.c) return b.c-a.c; // decreasing freq
return a.ch.charCodeAt(0)-b.ch.charCodeAt(0); // increasing ASCII
});
let res='';
for(const o of arr) res+=o.ch.repeat(o.c);
return res;
}
console.log(optimizeTransmission(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.