Custom Sort String - Practice Coding Problems

Custom Sort String - Problem

You are given two strings order and s. All characters in order are unique and represent a custom sorting order.

Your task is to permute the characters of string s so that they follow the custom order defined by order.

More specifically:

If character x appears before character y in order, then x should appear before y in the result string
Characters in s that don't appear in order can be placed anywhere in the result

Return any valid permutation of s that satisfies this property.

Input & Output

Example 1 — Basic Custom Order

$ Input: order = "cba", s = "abaccaba"

› Output: "ccbbaaaa"

💡 Note: Characters must follow order c→b→a. We have 2 c's, 2 b's, and 4 a's in s. Following the custom order: cc + bb + aaaa = "ccbbaaaa"

Example 2 — Extra Characters

$ Input: order = "cbafg", s = "abaccaba"

› Output: "ccbbaaaa"

💡 Note: String s contains only characters c, b, a which are all in order. Result follows c→b→a priority: "ccbbaaaa"

Example 3 — Characters Not in Order

$ Input: order = "kqep", s = "pekeq"

› Output: "kqeep"

💡 Note: Following order k→q→e→p: k(1) + q(1) + ee(2) + p(1) = "kqeep". All characters from s appear in order.

Constraints

1 ≤ order.length ≤ 26
1 ≤ s.length ≤ 200
order and s consist of lowercase English letters only
All characters of order are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Custom order and string to rearrange

Process

Rearrange characters following custom priority

Output

String with characters sorted by custom order

Key Takeaway

🎯 Key Insight: Count character frequencies first, then build result following the custom order sequence

Asked in

F Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is to use character frequency counting to avoid multiple scans. Count each character in string s, then build the result by following the order string and appending characters according to their frequency. Best approach uses frequency counting with Time: O(n + m), Space: O(k) where k is the number of unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Custom Comparator Sorting	O(m log m)	O(m)	Convert string to array, sort with custom comparator based on order string
Brute Force - Linear Search for Each Character	O(n×m)	O(1)	For each character in order, scan through s multiple times to find and collect all occurrences
Frequency Count (Optimal)	O(n + m)	O(k)	Count frequency of each character in s, then build result following order

Custom Comparator Sorting — Algorithm Steps

Create position map from order string
Convert s to character array
Sort array using custom comparator
Join sorted characters back to string

Visualization

Tap to expand

Step-by-Step Walkthrough

Map Positions

Assign priority numbers to each character

Sort

Sort characters by their priority

Reconstruct

Join sorted characters into result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    int pos;
} CharPos;

int orderMap[256];

int compare(const void* a, const void* b) {
    CharPos* charA = (CharPos*)a;
    CharPos* charB = (CharPos*)b;
    return charA->pos - charB->pos;
}

char* solution(char* order, char* s) {
    int orderLen = strlen(order);
    int sLen = strlen(s);
    
    // Initialize order map
    for (int i = 0; i < 256; i++) {
        orderMap[i] = orderLen; // Default for chars not in order
    }
    for (int i = 0; i < orderLen; i++) {
        orderMap[(int)order[i]] = i;
    }
    
    // Create array of character positions
    CharPos* chars = (CharPos*)malloc(sLen * sizeof(CharPos));
    for (int i = 0; i < sLen; i++) {
        chars[i].ch = s[i];
        chars[i].pos = orderMap[(int)s[i]];
    }
    
    // Sort by position
    qsort(chars, sLen, sizeof(CharPos), compare);
    
    // Build result string
    char* result = (char*)malloc((sLen + 1) * sizeof(char));
    for (int i = 0; i < sLen; i++) {
        result[i] = chars[i].ch;
    }
    result[sLen] = '\0';
    
    free(chars);
    return result;
}

int main() {
    char order[1001], s[1001];
    fgets(order, sizeof(order), stdin);
    fgets(s, sizeof(s), stdin);
    order[strcspn(order, "\n")] = 0;
    s[strcspn(s, "\n")] = 0;
    char* result = solution(order, s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m log m)

Sorting m characters in string s takes O(m log m) time

⚡ Linearithmic

Space Complexity

O(m)

Character array copy of string s plus position map

✓ Linear Space

182.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Custom Comparator Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler