Lexicographical Phrase Reconstructor — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n log n · L)

SpaceO(1) additional (ignoring recursion stack)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Lexicographical Phrase Reconstructor problem optimally.

TopicStrings

PatternMixed

TimeO(n log n · L)

SpaceO(1) additional (ignoring recursion stack)

Problem Description

Given an array of distinct strings, reorder the array so that the strings appear in strictly increasing lexicographical order according to ASCII values. In ASCII, the space character (code 32) precedes all alphanumeric characters, uppercase letters (code 65‑90) precede lowercase letters (code 97‑122), and comparison proceeds character by character. The content and case of each string must remain unchanged; only their positions may be altered. Return the reordered array.

DSA Pattern Breakdown

"Lexicographical Phrase Reconstructor"

medium

WHY DOES IT MATTER?

Lexicographical ordering under ASCII is a foundational pattern for any system that needs deterministic string keys—databases, caches, and distributed hash tables rely on it for range queries and sharding.

OPTIMIZATION CHALLENGE

The key insight is to avoid quadratic pairwise scans by using a divide‑and‑conquer sort that reduces the number of comparisons to O(n log n) while each comparison stops at the first mismatching character, preventing unnecessary full‑string scans.

REAL-WORLD CONNECTION

Think of a telephone directory where entries are sorted by the exact sequence of characters, including spaces; the same ordering determines how data is partitioned across servers in a sorted‑key store like Apache Cassandra.

When coding the comparator, fetch character codes once per index and break early on mismatch; also, pre‑check string lengths to handle prefix cases instantly—this tiny micro‑optimization often halves the runtime on large inputs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n · L)

💾 Space:O(1) additional (ignoring recursion stack)

Core Theory — Why This Approach?

Sorting a collection of strings in strict ASCII lexicographical order is a classic comparison‑based sorting problem. Each comparison proceeds character by character, using the numeric code of the character; spaces (32) come before digits and letters, uppercase (65‑90) before lowercase (97‑122). A naïve approach such as bubble‑sort or insertion‑sort runs in O(n²) time, which quickly becomes prohibitive when n reaches 10⁵ or when strings are long, because each pairwise comparison may scan many characters. The optimal paradigm leverages a divide‑and‑conquer sort (e.g., quicksort, mergesort, or heapsort) that guarantees O(n log n) comparisons, and each comparison costs O(L) where L is the length of the shorter string, yielding an overall O(N log n) where N is the total number of characters. Because the strings are distinct, stability is irrelevant, allowing in‑place implementations that keep auxiliary space to O(1) beyond the recursion stack.

Interview Questions on This Problem

Q1How would you sort an array of strings so that spaces are considered smaller than any alphanumeric character, without using language‑specific locale functions?

Implement a custom comparator that iterates over the two strings character by character, compares their ASCII codes (using charCodeAt in JavaScript or ord in Python), and returns the ordering based on the first differing code; if one string is a prefix of the other, the shorter string is considered smaller.

Q2A company asks you to sort up to 10⁶ distinct strings, each up to 200 characters long, within 2 seconds. Which sorting algorithm and implementation tricks would you choose?

Use an O(n log n) in‑place algorithm such as introsort (C++ std::sort) or Timsort (Python’s sorted) which are highly optimized; additionally, avoid creating temporary substrings during comparison, compare characters via direct index access, and, if memory permits, store the total length to short‑circuit comparisons when one string is a prefix of another.

Q3Explain how you could adapt radix sort to sort strings lexicographically under ASCII ordering and when it becomes advantageous over comparison‑based sorts.

Radix sort processes strings from the most significant character to the least, using counting sort for each character bucket (0‑127 for ASCII). It runs in O(N + k) time where N is total characters and k is the alphabet size (128). This becomes advantageous when strings are short and the dataset is massive, because it eliminates the log factor of comparison sorts, but it requires extra O(N) auxiliary space and careful handling of variable‑length strings by treating missing characters as a sentinel smaller than any real character.

Examples

Example 1

Input

["zoo","Apple"," banana","Cat"]

Output

[" banana","Apple","Cat","zoo"]

Explanation: The first character of each string is examined. A leading space (ASCII 32) is smallest, so " banana" comes first. Next, "Apple" starts with 'A' (65), then "Cat" with 'C' (67), and finally "zoo" with 'z' (122). The array is reordered accordingly.

Example 2

Input

["Hello World","hello world","Hello  world","HelloWorld"]

Output

["Hello  world","Hello World","HelloWorld","hello world"]

Explanation: Comparison proceeds left to right. "Hello world" has two consecutive spaces after "Hello", making it smaller than "Hello World" (single space then 'W'). "Hello World" is smaller than "HelloWorld" because a space (32) is less than 'W' (87). All strings beginning with uppercase 'H' are smaller than the one beginning with lowercase 'h' (104), so "hello world" is last.

Example 3

Input

["  leading","Trailing  ","Mid dle","NoSpace"]

Output

["  leading","Mid dle","NoSpace","Trailing  "]

Explanation: Strings are ordered by their first character. Two leading spaces (ASCII 32) make " leading" the smallest. The remaining strings start with 'M' (77), 'N' (78), and 'T' (84) respectively, giving the order "Mid dle", "NoSpace", "Trailing ". The final array reflects this ordering.

Constraints

1 <= strings.length <= 100000
Each string contains between 1 and 1000 ASCII characters inclusive
All strings are pairwise distinct
Total number of characters across all strings does not exceed 10^6

Optimal Approach & Strategy

Apply a standard O(n log n) comparison sort with a custom comparator that respects ASCII ordering, yielding near‑linear performance for large inputs.

Brute Force Approach

Repeatedly compare every pair of strings and swap them until the whole array is ordered, which is O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n log n · L)

function lexicographicalPhraseReconstructor(strs) {
    return strs.sort();
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
readline.on('line', line => {
    input.push(line);
}).on('close', () => {
    let n = parseInt(input[0]);
    let strs = input.slice(1, n + 1);
    let result = lexicographicalPhraseReconstructor(strs);
    console.log(result.join(' '));
});

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<std::string> lexicographicalPhraseReconstructor(std::vector<std::string>& strs) {
    std::sort(strs.begin(), strs.end());
    return strs;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<std::string> strs(n);
    for (int i = 0; i < n; i++) {
        std::cin >> strs[i];
    }
    std::vector<std::string> result = lexicographicalPhraseReconstructor(strs);
    for (const auto& str : result) {
        std::cout << str << " ";
    }
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static String[] lexicographicalPhraseReconstructor(String[] strs) {
        Arrays.sort(strs);
        return strs;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = scanner.next();
        }
        String[] result = lexicographicalPhraseReconstructor(strs);
        System.out.println(Arrays.toString(result).replaceAll("\\[\\]", "").replaceAll(",", ""));
    }
}

def lexicographical_phrase_reconstructor(strs):
    return sorted(strs)

if __name__ == "__main__":
    n = int(input())
    strs = [input() for _ in range(n)]
    result = lexicographical_phrase_reconstructor(strs)
    print(' '.join(result))

function lexicographicalPhraseReconstructor(strs) {
    return strs.sort();
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
readline.on('line', line => {
    input.push(line);
}).on('close', () => {
    let n = parseInt(input[0]);
    let strs = input.slice(1, n + 1);
    let result = lexicographicalPhraseReconstructor(strs);
    console.log(result.join(' '));
});

Asked in Top Tech Interviews

RazorpayOracle

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.