Generate Anagrammed IDs — Problem Statement & Solution Guide

StringsMediumTOOL RETURNED ID

TimeO(N·Lmax)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Generate Anagrammed IDs problem optimally.

TopicStrings

PatternTOOL RETURNED ID

TimeO(N·Lmax)

SpaceO(1)

Problem Description

Given three equally sized arrays—tools (array of strings), returned (array of strings) and ids (array of integers)—produce an array of identifiers. For each index i, concatenate tools[i], returned[i] and the decimal representation of ids[i] (in that order) to obtain a base string. Transform this base string into an identifier by sorting all its characters in non‑decreasing ASCII order (this yields a deterministic anagram). Return the identifiers in the original order of the input arrays. All input arrays have the same length N and N ≥ 1.

DSA Pattern Breakdown

"Generate Anagrammed IDs"

medium

WHY DOES IT MATTER?

Sorting characters to a canonical form enables constant‑time equality checks and is a classic technique for anagram detection, which appears in many coding interviews and real‑world deduplication pipelines.

OPTIMIZATION CHALLENGE

Recognizing that the alphabet size is fixed allows us to replace O(L log L) sorting with O(L) counting sort, collapsing the dominant factor and turning a potentially quadratic‑ish solution into linear time.

REAL-WORLD CONNECTION

Think of a distributed hash table that stores files by their content fingerprint; sorting the bytes of a file creates a deterministic fingerprint regardless of ordering, similar to how this problem creates a stable identifier from unordered character permutations.

When coding, allocate a single int[256] buffer once and zero it with memset for each element; this avoids repeated allocations and keeps the constant factor low, which interviewers love to see.

COMPLEXITY AT A GLANCE

⏱ Time:O(N·Lmax)

💾 Space:O(1)

Core Theory — Why This Approach?

The task reduces to a per‑element transformation where the key operation is sorting the characters of a concatenated string. A naïve implementation would invoke a comparison‑based sort (e.g., quicksort) on each string, yielding O(L log L) time per element, which quickly becomes prohibitive when N and the average length L grow large. Because the character set is bounded to ASCII (0‑127), we can replace the generic sort with a linear‑time counting sort: we count occurrences of each character, then reconstruct the sorted string by iterating over the count array. This brings the per‑element cost down to O(L) while using O(1) auxiliary space (a fixed‑size 256‑element array). The overall algorithm therefore runs in O(N·Lmax) time, optimal up to a constant factor, and scales gracefully for massive inputs.

The optimal paradigm here is “frequency‑based sorting” (also known as counting sort) applied to strings. It exploits the limited alphabet size to avoid the log factor inherent in comparison sorts. By processing each index independently and reusing a pre‑allocated count buffer, we also achieve excellent cache locality, which is crucial in high‑throughput interview settings where constant‑factor performance often matters more than asymptotic notation alone.

Interview Questions on This Problem

Q1How would you generate the identifier for each index if the character set could include Unicode beyond ASCII?

Switch to a stable O(L log U) sort where U is the number of distinct Unicode code points in the string, or use a radix sort on UTF‑8 bytes; counting sort is no longer O(1) space because the alphabet size is unbounded.

Q2What modifications are needed if the ids array can contain negative integers?

Convert the integer to its signed decimal representation (including the leading ‘‑’ sign) before concatenation; the counting sort naturally handles the ‘‑’ character as any other ASCII symbol.

Q3Can you compute all identifiers in parallel? What considerations arise?

Yes—each index is independent, so a thread‑pool or SIMD batch can process chunks concurrently. The main concern is avoiding false sharing on the shared count buffer; allocate a private count array per thread or use lock‑free accumulation.

Examples

Example 1

Input

tools = ["hammer","saw"], returned = ["no","yes"], ids = [12,305]

Output

["112aehmmnr","0035aessy"]

Explanation: Index 0: "hammer"+"no"+"12" = "hammerno12". Sorting characters gives "112aehmmnr". Index 1: "saw"+"yes"+"305" = "sawyes305". Sorting yields "0035aessy".

Example 2

Input

tools = ["drill"], returned = ["ok"], ids = [7]

Output

["7dikllor"]

Explanation: Concatenate "drill"+"ok"+"7" = "drillok7". Sorted characters produce "7dikllor".

Example 3

Input

tools = ["wrench","pliers","chisel"], returned = ["yes","no","maybe"], ids = [1001,42,777]

Output

["0011cehnrwsy","024ilprss"]

Explanation: Index 0: "wrench"+"yes"+"1001" = "wrenchyes1001" → sorted "0011cehnrwsy". Index 1: "pliers"+"no"+"42" = "pliersno42" → sorted "024ilprss". Index 2: "chisel"+"maybe"+"777" = "chiselmaybe777" → sorted "777abceehiilmss" (omitted from output to keep example concise).

Constraints

1 <= N <= 10^5
Each tool string length is between 1 and 20 characters
Each returned string length is between 1 and 10 characters
0 <= ids[i] <= 10^9
All characters are standard printable ASCII

Optimal Approach & Strategy

Use a fixed‑size 256‑element frequency array to count characters and rebuild the string in order, achieving O(L) time per element with O(1) extra space.

Brute Force Approach

Concatenate the three parts and call a generic sort like JavaScript's .sort() on the character array, which costs O(L log L) per element.

Code Solutions

Language:

JavaScript Solution

Time: O(N·Lmax)

function generateAnagrammedIds(tools, returned, ids) {
    return tools.map((tool, index) => {
        const baseString = tool + returned[index] + ids[index];
        return [...baseString].sort().join('');
    });
}

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

let input = [];
readline.on('line', (line) => {
    input.push(line);
});

readline.on('close', () => {
    const n = parseInt(input[0]);
    const tools = [];
    const returned = [];
    const ids = [];

    for (let i = 1; i <= n; i++) {
        const [tool, ret, id] = input[i].split(' ');
        tools.push(tool);
        returned.push(ret);
        ids.push(parseInt(id));
    }

    const result = generateAnagrammedIds(tools, returned, ids);
    console.log(result.join('\n'));
});


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

std::vector<std::string> generateAnagrammedIds(std::vector<std::string>& tools, std::vector<std::string>& returned, std::vector<int>& ids) {
    std::vector<std::string> result;
    for (int i = 0; i < tools.size(); i++) {
        std::string baseString = tools[i] + returned[i] + std::to_string(ids[i]);
        std::string anagrammedId = baseString;
        std::sort(anagrammedId.begin(), anagrammedId.end());
        result.push_back(anagrammedId);
    }
    return result;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<std::string> tools(n);
    std::vector<std::string> returned(n);
    std::vector<int> ids(n);

    for (int i = 0; i < n; i++) {
        std::cin >> tools[i] >> returned[i] >> ids[i];
    }

    std::vector<std::string> result = generateAnagrammedIds(tools, returned, ids);

    for (const auto& str : result) {
        std::cout << str << std::endl;
    }

    return 0;
}


import java.util.*;

public class Main {
    public static List<String> generateAnagrammedIds(String[] tools, String[] returned, int[] ids) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < tools.length; i++) {
            String baseString = tools[i] + returned[i] + ids[i];
            char[] chars = baseString.toCharArray();
            Arrays.sort(chars);
            result.add(new String(chars));
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume newline left-over

        String[] tools = new String[n];
        String[] returned = new String[n];
        int[] ids = new int[n];

        for (int i = 0; i < n; i++) {
            String[] parts = scanner.nextLine().split(" ");
            tools[i] = parts[0];
            returned[i] = parts[1];
            ids[i] = Integer.parseInt(parts[2]);
        }

        List<String> result = generateAnagrammedIds(tools, returned, ids);
        for (String str : result) {
            System.out.println(str);
        }
    }
}


def generate_anagrammed_ids(tools, returned, ids):
    return [''.join(sorted(tool + ret + str(id))) for tool, ret, id in zip(tools, returned, ids)]

if __name__ == "__main__":
    n = int(input())
    tools = []
    returned = []
    ids = []

    for _ in range(n):
        tool, ret, id = input().split()
        tools.append(tool)
        returned.append(ret)
        ids.append(int(id))

    result = generate_anagrammed_ids(tools, returned, ids)
    for res in result:
        print(res)


function generateAnagrammedIds(tools, returned, ids) {
    return tools.map((tool, index) => {
        const baseString = tool + returned[index] + ids[index];
        return [...baseString].sort().join('');
    });
}

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

let input = [];
readline.on('line', (line) => {
    input.push(line);
});

readline.on('close', () => {
    const n = parseInt(input[0]);
    const tools = [];
    const returned = [];
    const ids = [];

    for (let i = 1; i <= n; i++) {
        const [tool, ret, id] = input[i].split(' ');
        tools.push(tool);
        returned.push(ret);
        ids.push(parseInt(id));
    }

    const result = generateAnagrammedIds(tools, returned, ids);
    console.log(result.join('\n'));
});

Asked in Top Tech Interviews

Cred

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.