Galactic Translator — Problem Statement & Solution Guide
Problem Description
Given a lowercase string s, decide whether its characters can be permuted to form a strictly increasing alphabetical sequence where each character is the immediate successor of the previous one (e.g., "abc" or "fghijk"). The sequence must contain the consecutive pair "jk" (i.e., a 'j' immediately followed by a 'k'). Output "YES" if such a permutation exists, otherwise output "NO".
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Translator"
WHY DOES IT MATTER?
Recognizing the "consecutive characters" pattern lets you replace exponential permutation checks with linear scans, a skill that appears in many coding interviews involving strings and arrays.
OPTIMIZATION CHALLENGE
The key insight is that the existence of a valid permutation depends only on character frequencies and the min‑max range, not on the order of characters, collapsing the problem to constant‑size bookkeeping.
REAL-WORLD CONNECTION
Think of allocating contiguous memory blocks in a distributed cache: you need a range of free slots that are sequential and include a specific key (like 'jk') before you can place data efficiently.
During the interview, first verify uniqueness and range length before checking for 'j' and 'k'—this ordering lets you fail fast and keeps the code clean.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to checking whether the multiset of characters in the input string can be rearranged into a contiguous segment of the alphabet. A naive solution would try all permutations, which is factorial in the length of the string and impossible for n>10. The optimal paradigm leverages counting sort principles: by counting occurrences of each letter we can instantly verify uniqueness, compute the smallest and largest letters, and confirm that the range size matches the number of distinct characters, guaranteeing consecutiveness. The additional requirement that the sequence contain the pair "jk" is satisfied automatically if both letters exist, because in any strictly increasing consecutive arrangement they will be adjacent. This transforms the problem into O(n) scanning and O(1) auxiliary storage (26‑size array).
Interview Questions on This Problem
Q1How would you determine if a string can be permuted into a strictly increasing consecutive alphabet sequence containing "jk"?
Count each character, ensure every count is 1, find the minimum and maximum characters, verify max‑min+1 equals the number of distinct characters, and confirm both 'j' and 'k' are present.
Q2Why is a frequency array of size 26 sufficient for this problem, and what would change if the input could contain uppercase letters?
Because the input is limited to lowercase English letters, a fixed 26‑element array gives O(1) access to each character’s count. With uppercase letters you’d need a 52‑element array or map, but the algorithmic idea stays the same.
Q3Explain how you would extend the solution to handle strings that may contain duplicate characters while still requiring a strictly increasing sequence without repeats.
First, detect any count >1 and immediately return "NO" because a strictly increasing sequence cannot have duplicates; the rest of the checks remain identical.
Examples
Input
kfjghi
Output
YES
Explanation: The letters can be reordered as "fghijk". Every adjacent pair differs by exactly one in the alphabet (f→g, g→h, h→i, i→j, j→k) and the required "jk" appears.
Input
abdef
Output
NO
Explanation: The set of letters lacks 'c', so no permutation can produce a contiguous alphabetical block; therefore the condition cannot be satisfied.
Input
mnopqr
Output
NO
Explanation: Although the letters are consecutive, the mandatory "jk" pair is absent, so the required pattern cannot be achieved.
Constraints
- 1 <= s.length <= 100000
- s consists only of lowercase English letters
Optimal Approach & Strategy
Count characters, check uniqueness, compute min/max, validate range length, and ensure 'j' and 'k' are present—linear time, constant space.
Brute Force Approach
Generate every permutation of the string and test each for a consecutive alphabet sequence containing "jk"—exponential time.
Verified Code Solutions
function solve(s) {
const n = s.length;
if (n < 2) return "NO";
const freq = new Array(26).fill(0);
for (const ch of s) {
const idx = ch.charCodeAt(0) - 97;
freq[idx]++;
if (freq[idx] > 1) return "NO";
}
let minc = 26, maxc = -1;
for (let i = 0; i < 26; i++) if (freq[i]) {
if (i < minc) minc = i;
if (i > maxc) maxc = i;
}
if (maxc - minc + 1 !== n) return "NO";
if (freq['j'.charCodeAt(0)-97] === 0 || freq['k'.charCodeAt(0)-97] === 0) return "NO";
return "YES";
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) console.log(solve(input));#include <bits/stdc++.h>
using namespace std;
string solve(const string& s) {
int n = s.size();
if (n < 2) return "NO";
vector<int> freq(26,0);
for(char c: s){
int idx = c - 'a';
if(++freq[idx] > 1) return "NO";
}
int minc = 26, maxc = -1;
for(int i=0;i<26;i++) if(freq[i]){
minc = min(minc,i);
maxc = max(maxc,i);
}
if (maxc - minc + 1 != n) return "NO";
if (freq['j'-'a']==0 || freq['k'-'a']==0) return "NO";
return "YES";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; if(!(cin>>s)) return 0;
cout<<solve(s);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
static String solve(String s) {
int n = s.length();
if (n < 2) return "NO";
int[] freq = new int[26];
for (char c : s.toCharArray()) {
int idx = c - 'a';
freq[idx]++;
if (freq[idx] > 1) return "NO";
}
int minc = 26, maxc = -1;
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
if (i < minc) minc = i;
if (i > maxc) maxc = i;
}
}
if (maxc - minc + 1 != n) return "NO";
if (freq['j' - 'a'] == 0 || freq['k' - 'a'] == 0) return "NO";
return "YES";
}
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(solve(s.trim()));
}
}
}def solve(s: str) -> str:
n = len(s)
if n < 2:
return "NO"
freq = [0] * 26
for ch in s:
idx = ord(ch) - 97
freq[idx] += 1
if freq[idx] > 1:
return "NO"
# find min and max present characters
minc = next(i for i, v in enumerate(freq) if v)
maxc = next(i for i in range(25, -1, -1) if freq[i])
if maxc - minc + 1 != n:
return "NO"
if freq[ord('j') - 97] == 0 or freq[ord('k') - 97] == 0:
return "NO"
return "YES"
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip()
if data:
print(solve(data))function solve(s) {
const n = s.length;
if (n < 2) return "NO";
const freq = new Array(26).fill(0);
for (const ch of s) {
const idx = ch.charCodeAt(0) - 97;
freq[idx]++;
if (freq[idx] > 1) return "NO";
}
let minc = 26, maxc = -1;
for (let i = 0; i < 26; i++) if (freq[i]) {
if (i < minc) minc = i;
if (i > maxc) maxc = i;
}
if (maxc - minc + 1 !== n) return "NO";
if (freq['j'.charCodeAt(0)-97] === 0 || freq['k'.charCodeAt(0)-97] === 0) return "NO";
return "YES";
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) console.log(solve(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.