Loading…

mediumStringsSometimes asked

Lexicographic Rank of a String

Q: How do you solve Lexicographic Rank of a String using the Brute Force — Generate and Sort Permutations approach?

When to use it: Say it first to nail the definition of rank, then point out the n! blow-up that forces the combinatorial formula. The definition-driven baseline literally builds the dictionary. **The literal method.** Produce all permutations of the characters, drop duplicates into a sorted structure, and find where `s` lands. Its 1-based position is the rank. **Why dedup matters.** With repeated characters, naive permutation generation yields the same string multiple times. A set (or sorted unique list) collapses those so each distinct arrangement counts once — matching the problem's definition. **Why it can't scale.** The number of permutations is `n!` (or `n!/Πfreq!` distinct ones). For `n = 12` that's already ~479 million. Generating and sorting them is hopeless past tiny `n`. The value of this approach is purely as a correctness oracle and as a way to *see* that rank = (position in the sorted list) + 1 — the very quantity the combinatorial formula computes directly. Time complexity: O(n! · n log(n!)). Space complexity: O(n! · n).

Arrays & Hashing · 37 of 83 · 12 min

Given a string s, return its 1-based rank among all distinct permutations of its characters, listed in lexicographic (dictionary) order.

The smallest permutation has rank 1. If s contains repeated characters, count each distinct arrangement once.

In plain English

Lay out every distinct rearrangement of the characters in dictionary order and ask which line the given string falls on. Instead of generating that list, count — for each position — how many permutations begin with a smaller-but-valid character, because all of those come earlier. Duplicates mean some arrangements coincide, so the per-block factorial must be deflated by the repeated counts.

Examples

Example 1

Input: s = "acb"
Output: 2
Note: Permutations sorted: abc, acb, bac, bca, cab, cba. "acb" is the 2nd → rank 2. At position 0, 'a' has nothing smaller to its right; at position 1, 'c' has 'b' smaller to its right → 1 × 1! = 1; plus 1 = 2.

Example 2

Input: s = "string"
Output: 598
Note: All characters distinct; apply rank = 1 + Σ smallerRight(i) × (5−i)!.

Example 3

Input: s = "aba"
Output: 2
Note: Distinct permutations sorted: aab, aba, baa. "aba" is 2nd. Duplicate 'a' forces dividing each block by 2! where the suffix still holds two a's.

Constraints

1 ≤ n ≤ 20 if using 64-bit factorials; larger n needs big integers or modular arithmetic
Characters are ASCII (commonly lowercase letters)
Rank counts only *distinct* permutations
Rank is 1-based

Clarifying questions4First question: Is the rank 0-based or 1-based?Explore questions

Q1.Is the rank 0-based or 1-based?
1-based by convention — the smallest permutation is rank 1. Confirm, because it changes only the final +1.
Q2.Can the string have duplicate characters?
Yes, and it matters: identical arrangements must be counted once, which means dividing each factorial block by the factorials of the repeated counts.
Q3.How large can n be?
If n ≤ 20, factorials fit in 64-bit. Beyond that, use big integers or compute the rank modulo a large prime with modular inverses.
Q4.Are we ranking among permutations or among all strings of that length?
Among permutations of the given multiset of characters. Ranking among all length-n strings is a different, base-Σ counting problem.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the 1-based rank of a string among all its permutations in dictionary order. For each position, count how many characters to its right are smaller — each such smaller character could lead a block of (remaining-length)! permutations that all sort before the given string. Sum those blocks and add 1. With duplicate characters you must divide each block by the factorials of the repeated counts. Distinct case is O(n²) or O(n·26); answer rank = 1 + Σ (smaller-to-right) × (remaining)!.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can convert 'position in sorted order' into a per-position combinatorial count, and whether you correctly divide by repeated-character factorials instead of assuming all characters are distinct.

Where candidates slip

Counting smaller characters over the whole string instead of only to the right, forgetting the +1 for 1-based rank, or ignoring duplicates and over-counting.

How to stand out

Derive the formula from the factorial number system, handle duplicates with the Π freq! division, and flag the overflow with a modular-inverse or big-integer plan.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Generate and Sort Permutations	`O(n! · n log(n!))`	`O(n! · n)`	Say it first to nail the definition of rank, then point out the n! blow-up that forces the combinatorial formula.	Read
2	Factorial Counting with Duplicate Handling (Optimal)Optimal	`O(n² ) or O(n·Σ)`	`O(Σ)`	The intended answer. Derive it from the factorial number system and handle duplicates with the Π freq! division.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAt position i, char s[i]Duplicates?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Generate and Sort Permutations

TimeO(n! · n log(n!))SpaceO(n! · n)

Say it first to nail the definition of rank, then point out the n! blow-up that forces the combinatorial formula.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Generate every distinct permutation, sort them lexicographically, and the index of s (plus 1) is the rank.

2Hint 2Explore hint

Deduplicate with a set so repeated characters don't inflate the count.

3Hint 3Explore hint

There are up to n! permutations — this is only viable for very small n, but it nails down exactly what 'rank' means.

A · Core idea

The definition-driven baseline literally builds the dictionary.

The literal method. Produce all permutations of the characters, drop duplicates into a sorted structure, and find where s lands. Its 1-based position is the rank.

Why dedup matters. With repeated characters, naive permutation generation yields the same string multiple times. A set (or sorted unique list) collapses those so each distinct arrangement counts once — matching the problem's definition.

Why it can't scale. The number of permutations is n! (or n!/Πfreq! distinct ones). For n = 12 that's already ~479 million. Generating and sorting them is hopeless past tiny n. The value of this approach is purely as a correctness oracle and as a way to see that rank = (position in the sorted list) + 1 — the very quantity the combinatorial formula computes directly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "acb"

Array state

sorted

abc, acb, bac, bca, cab, cba

abc

[0]

s ↓

acb

[1]

bac

[2]

bca

[3]

cab

[4]

cba

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewimport java.util.TreeSet; public class BruteForceRank { private final TreeSet<String> perms = new TreeSet<>(); Explore the full code

solution.javaJava

Brute Force — Generate and Sort Permutations — reference

2 teaching notes

1
import java.util.TreeSet;
2
 
3
public class BruteForceRank {
4
    // TreeSet keeps permutations sorted and deduplicated in one structure.
5
    private final TreeSet<String> perms = new TreeSet<>();
6
 
7
    public long rank(String s) {
8
        perms.clear();
9
        permute(s.toCharArray(), 0);
10
        long r = 1;
11
        for (String p : perms) {
12
            // Position in sorted order (1-based) is the rank.
13
            if (p.equals(s)) return r;
14
            r++;
15
        }
16
        return -1;
17
    }
18
 
19
    private void permute(char[] a, int k) {
20
        if (k == a.length) { perms.add(new String(a)); return; }
21
        for (int i = k; i < a.length; i++) {
22
            swap(a, k, i);
23
            permute(a, k + 1);
24
            swap(a, k, i);
25
        }
26
    }
27
 
28
    private void swap(char[] a, int i, int j) { char t = a[i]; a[i] = a[j]; a[j] = t; }
29
 
30
    public static void main(String[] args) {
31
        System.out.println(new BruteForceRank().rank("acb"));
32
    }
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n! · n log(n!)) timeO(n! · n) spaceOpen the invariant and proofExplore the proof

Brute force shows that rank equals the count of distinct permutations strictly smaller than s, plus one. The optimal approach computes that count without materializing the list — by counting, position by position, how many smaller permutations exist.

ComplexityO(n! · n log(n!)) time, O(n! · n) space — Generating permutations is O(n!) of them, each of length n; sorting that many length-n strings is O(n! · n log(n!)). Storing them is O(n! · n). Factorial growth caps this at roughly n ≤ 10.

E · Edge cases and pitfalls3Not deduplicating — repeated characters inflate the rank.Explore edge cases

Pitfalls

Not deduplicating — repeated characters inflate the rank.
Returning a 0-based index — off by one from the expected 1-based rank.
Trying it for n beyond ~10 — n! permutations exhaust time and memory.

03.2

Approach 2 of 2 · Optimal

Factorial Counting with Duplicate Handling (Optimal)

TimeO(n² ) or O(n·Σ)SpaceO(Σ)

The intended answer. Derive it from the factorial number system and handle duplicates with the Π freq! division.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk left to right. At position i, every permutation that puts a character smaller than s[i] here (and is otherwise any arrangement of the rest) sorts before s. How many such arrangements are there?

2Hint 2Explore hint

If the remaining characters are all distinct, fixing one smaller character leaves (n-1-i)! arrangements. Sum (count of smaller chars to the right) × (n-1-i)! over all i, then add 1.

3Hint 3Explore hint

With duplicates, (n-1-i)! over-counts because swapping identical characters yields the same string. Divide by the product of factorials of the remaining character frequencies.

A · Core idea

The optimal solution counts the permutations smaller than s directly, treating the answer as a number written in the factorial base.

The per-position question. Scan s left to right. Standing at position i, ask: how many distinct permutations agree with s on positions 0..i−1 but place a smaller character at position i? Every such permutation is lexicographically less than s, and every permutation less than s is captured at exactly one such position (the first place it diverges). So summing these counts over all i gives the number of permutations before s; add 1 for the 1-based rank.

Counting one position (distinct case). Let smaller = the number of characters strictly less than s[i] among the remaining characters (positions i..n−1). Choosing any one of those smaller characters to sit at position i leaves n−1−i characters to arrange freely, which is (n−1−i)! orderings. So position i contributes smaller × (n−1−i)!.

The duplicate correction. When the remaining characters contain repeats, (n−1−i)! counts arrangements that are actually identical (swapping two equal characters changes nothing). The number of distinct arrangements of a multiset with frequencies freq[c] is (n−1−i)! / Π_c freq[c]!. So each block becomes smaller × (n−1−i)! / Π_c freq[c]!, where freq is the frequency table of the suffix s[i..n−1]. After processing position i, decrement freq[s[i]] so the table always reflects 'characters still available'.

Why this is the factorial number system. The sequence of smaller counts is exactly the factorial-base digits of rank − 1: digit i lies in [0, n−1−i] and carries weight (n−1−i)!. Ranking a permutation is reading off those digits; un-ranking (finding the k-th permutation) is the inverse.

Overflow reality. Factorials grow past 64-bit at 21!. For larger inputs, either use big integers, or — if only rank mod M is needed — precompute factorials and modular inverses modulo a prime so the division by Π freq! becomes multiplication by modular inverses.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba"

Array state

i=0 'a'

smaller to right = 0 → 0 × 2! = 0

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Factorial Counting with Duplicate Handling (Optimal) — optimal

5 teaching notes

1
import java.math.BigInteger;
2
 
3
public class LexRank {
4
    public BigInteger rank(String s) {
5
        int n = s.length();
6
        BigInteger[] fact = new BigInteger[n + 1];
7
        fact[0] = BigInteger.ONE;
8
        // Precompute factorials as BigInteger so 21! and beyond don't overflow.
9
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i));
10
 
11
        int[] freq = new int[256];
12
        for (int i = 0; i < n; i++) freq[s.charAt(i)]++;
13
 
14
        BigInteger rank = BigInteger.ZERO;
15
        for (int i = 0; i < n; i++) {
16
            char c = s.charAt(i);
17
            long smaller = 0;
18
            // Count characters strictly smaller than s[i] still available in the
19
            // suffix.
20
            for (int ch = 0; ch < c; ch++) smaller += freq[ch];
21
 
22
            BigInteger denom = BigInteger.ONE;
23
            for (int ch = 0; ch < 256; ch++) denom = denom.multiply(fact[freq[ch]]);
24
 
25
            // block = smaller * (n-1-i)! / Pi freq! : permutations diverging here and going smaller
26
            BigInteger block = BigInteger.valueOf(smaller)
27
                .multiply(fact[n - 1 - i])
28
                .divide(denom);
29
            rank = rank.add(block);
30
 
31
            // Consume s[i]; the suffix multiset shrinks before the next position.
32
            freq[c]--;
33
        }
34
        // +1 converts the count-of-smaller into a 1-based rank.
35
        return rank.add(BigInteger.ONE);
36
    }
37
 
38
    public static void main(String[] args) {
39
        System.out.println(new LexRank().rank("aba"));
40
        System.out.println(new LexRank().rank("string"));
41
    }
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(n² ) or O(n·Σ) timeO(Σ) spaceOpen the invariant and proofExplore the proof

Rank is a counting problem, not a sorting problem. Each position contributes an independent block of 'permutations that diverge here and go smaller', and the factorial weight is just the number of ways to fill the tail. Duplicates only change the weight by deflating it with Π freq! — the structure is identical.

ComplexityO(n² ) or O(n·Σ) time, O(Σ) space — For each of the n positions you count smaller characters in the suffix (O(Σ) with a frequency table, or O(n) by scanning), and compute a factorial-ratio block. That's O(n·Σ) or O(n²). The frequency table is O(Σ) space; factorials are precomputed in O(n).

E · Edge cases and pitfalls7s = "a" — Single character → only permutation → rank 1.Explore edge cases

Edge cases handled

s = "a"Single character → only permutation → rank 1.
s = "cba"Largest permutation of {a,b,c} → rank 6 (= 3!).
s = "aaa"Only one distinct permutation → rank 1; duplicate division cancels everything.

Pitfalls

Counting smaller characters over the whole string instead of only the suffix.
Ignoring duplicates — without the Π freq! division you over-count and inflate the rank.
Using 64-bit factorials beyond 20! — silent overflow to wrong (often negative) values.
Forgetting the +1, returning a 0-based count instead of a rank.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.math.BigInteger; public class LexRank { public BigInteger rank(String s) { int n = s.length();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.math.BigInteger;

public class LexRank {
    public BigInteger rank(String s) {
        int n = s.length();
        BigInteger[] fact = new BigInteger[n + 1];
        fact[0] = BigInteger.ONE;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i));

int[] freq = new int[256];
        for (int i = 0; i < n; i++) freq[s.charAt(i)]++;

BigInteger rank = BigInteger.ZERO;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            long smaller = 0;
            for (int ch = 0; ch < c; ch++) smaller += freq[ch];

BigInteger denom = BigInteger.ONE;
            for (int ch = 0; ch < 256; ch++) denom = denom.multiply(fact[freq[ch]]);

// block = smaller * (n-1-i)! / Pi freq! : permutations diverging here and going smaller
            BigInteger block = BigInteger.valueOf(smaller)
                .multiply(fact[n - 1 - i])
                .divide(denom);
            rank = rank.add(block);

freq[c]--;
        }
        return rank.add(BigInteger.ONE);
    }

public static void main(String[] args) {
        System.out.println(new LexRank().rank("aba"));
        System.out.println(new LexRank().rank("string"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Smaller count over the whole string

Only characters still available (to the right) can validly sit at position i. Counting smaller characters that already appeared in the prefix double-counts and corrupts the rank.

Explore the code comparison

Don't write this

smaller = sum(1 for ch in s if ch < s[i])   # whole string — wrong

Write this instead

smaller = sum(freq[ch] for ch in range(ord(s[i])))  # only remaining suffix

Ignoring duplicate characters

(n-1-i)! counts arrangements that are identical when characters repeat. Without dividing by Π freq! the block over-counts and the rank comes out too large.

Explore the code comparison

Don't write this

block = smaller * factorial(n - 1 - i)            # over-counts duplicates

Write this instead

denom = 1
for f in freq:
    denom *= factorial(f)
block = smaller * factorial(n - 1 - i) // denom

64-bit factorial overflow

21! exceeds the 64-bit range, so for longer strings the factorial silently wraps and every block is wrong. Use big integers or modular arithmetic.

Explore the code comparison

Don't write this

long f = 1; for (int k = 2; k <= n; k++) f *= k; // overflows at 21!

Write this instead

BigInteger f = BigInteger.ONE;
for (int k = 2; k <= n; k++) f = f.multiply(BigInteger.valueOf(k));

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Factorial number system: count permutations that sort before each prefix

Code pattern to memorize

DISTINCT:   rank = 1 + Σ_i  smallerRight(i) * (n-1-i)!
WITH DUPLICATES: rank = 1 + Σ_i  smallerRight(i) * (n-1-i)! / Π_c (freq[c]!)
  where freq is the frequency of the suffix s[i..n-1], updated as you advance

Rules to remember

1Rank is 1-based — the smallest permutation has rank 1, so the final answer adds 1.
2smallerRight(i) counts characters strictly less than s[i] among positions i+1..n-1, not the whole string.
3Each smaller character fixes position i and frees (n-1-i)! arrangements of the rest — that's why the factorial appears.
4Duplicates: divide each block by Π freq[c]! over the current suffix multiset, or you over-count identical arrangements.
5Factorials explode — 21! overflows 64-bit. Use big integers, or compute the rank modulo a prime with modular inverses.

Use this pattern when

Rank / un-rank a permutation in lexicographic order
Map a permutation to/from an index (factorial number system)
Find the k-th permutation, or how many permutations precede a given one
Any 'position in dictionary of all rearrangements' question

Choose another pattern when

You only need the *next* permutation → next_permutation in-place swap, not full ranking
Alphabet/length tiny and you just need any one answer → brute force all permutations
Strings are not permutations of each other → ranking among permutations is undefined
You need rank among arbitrary strings of a length, not permutations → positional base-Σ counting instead

Interview takeaway

Lexicographic rank is the factorial number system in disguise: digit i is 'how many unused smaller characters remain', weighted by the factorial of the remaining length. Duplicates just divide out the indistinguishable rearrangements.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFactorial Number System / combinatorial ranking. Recognise it whenever a problem asks for the position of a permutation in sorted order, the k-th permutation, or how many arrangements precede one — all are factorial-base digit reads, with duplicates handled by dividing out Π freq!.

Practice queueDirect variations and pattern siblings

Direct follow-ups

k-th Permutation Sequence (un-rank)
Coming soon
Invert the formula: peel off factorial-base digits of k−1 to pick each character in turn.
Next Permutation
Coming soon
If you only need the immediately following permutation, do the in-place pivot-swap-reverse in O(n).
Rank of a String mod p (large n)
Coming soon
Precompute factorials and modular inverses; replace division by Π freq! with multiplication by inverses.
Rank Among All Strings of Length n
Coming soon
Not a permutation problem — use positional base-Σ counting instead of factorials.

Same pattern

←

Count Distinct Substrings

Continue · Next problem

Longest Palindromic Substring — Manacher's Algorithm

mediumStringsSometimes asked

Lexicographic Rank of a String

Arrays & Hashing · 37 of 83 · 12 min

Given a string s, return its 1-based rank among all distinct permutations of its characters, listed in lexicographic (dictionary) order.

The smallest permutation has rank 1. If s contains repeated characters, count each distinct arrangement once.

In plain English

Examples

Example 1

Input: s = "acb"
Output: 2
Note: Permutations sorted: abc, acb, bac, bca, cab, cba. "acb" is the 2nd → rank 2. At position 0, 'a' has nothing smaller to its right; at position 1, 'c' has 'b' smaller to its right → 1 × 1! = 1; plus 1 = 2.

Example 2

Input: s = "string"
Output: 598
Note: All characters distinct; apply rank = 1 + Σ smallerRight(i) × (5−i)!.

Example 3

Input: s = "aba"
Output: 2
Note: Distinct permutations sorted: aab, aba, baa. "aba" is 2nd. Duplicate 'a' forces dividing each block by 2! where the suffix still holds two a's.

Constraints

1 ≤ n ≤ 20 if using 64-bit factorials; larger n needs big integers or modular arithmetic
Characters are ASCII (commonly lowercase letters)
Rank counts only *distinct* permutations
Rank is 1-based

Clarifying questions4First question: Is the rank 0-based or 1-based?Explore questions

Q1.Is the rank 0-based or 1-based?
1-based by convention — the smallest permutation is rank 1. Confirm, because it changes only the final +1.
Q2.Can the string have duplicate characters?
Yes, and it matters: identical arrangements must be counted once, which means dividing each factorial block by the factorials of the repeated counts.
Q3.How large can n be?
If n ≤ 20, factorials fit in 64-bit. Beyond that, use big integers or compute the rank modulo a large prime with modular inverses.
Q4.Are we ranking among permutations or among all strings of that length?
Among permutations of the given multiset of characters. Ranking among all length-n strings is a different, base-Σ counting problem.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Counting smaller characters over the whole string instead of only to the right, forgetting the +1 for 1-based rank, or ignoring duplicates and over-counting.

How to stand out

Derive the formula from the factorial number system, handle duplicates with the Π freq! division, and flag the overflow with a modular-inverse or big-integer plan.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Generate and Sort Permutations	`O(n! · n log(n!))`	`O(n! · n)`	Say it first to nail the definition of rank, then point out the n! blow-up that forces the combinatorial formula.	Read
2	Factorial Counting with Duplicate Handling (Optimal)Optimal	`O(n² ) or O(n·Σ)`	`O(Σ)`	The intended answer. Derive it from the factorial number system and handle duplicates with the Π freq! division.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Generate and Sort Permutations

TimeO(n! · n log(n!))SpaceO(n! · n)

Say it first to nail the definition of rank, then point out the n! blow-up that forces the combinatorial formula.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Generate every distinct permutation, sort them lexicographically, and the index of s (plus 1) is the rank.

2Hint 2Explore hint

Deduplicate with a set so repeated characters don't inflate the count.

3Hint 3Explore hint

There are up to n! permutations — this is only viable for very small n, but it nails down exactly what 'rank' means.

A · Core idea

The definition-driven baseline literally builds the dictionary.

The literal method. Produce all permutations of the characters, drop duplicates into a sorted structure, and find where s lands. Its 1-based position is the rank.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "acb"

Array state

sorted

abc, acb, bac, bca, cab, cba

abc

[0]

s ↓

acb

[1]

bac

[2]

bca

[3]

cab

[4]

cba

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewimport java.util.TreeSet; public class BruteForceRank { private final TreeSet<String> perms = new TreeSet<>(); Explore the full code

solution.javaJava

Brute Force — Generate and Sort Permutations — reference

2 teaching notes

1
import java.util.TreeSet;
2
 
3
public class BruteForceRank {
4
    // TreeSet keeps permutations sorted and deduplicated in one structure.
5
    private final TreeSet<String> perms = new TreeSet<>();
6
 
7
    public long rank(String s) {
8
        perms.clear();
9
        permute(s.toCharArray(), 0);
10
        long r = 1;
11
        for (String p : perms) {
12
            // Position in sorted order (1-based) is the rank.
13
            if (p.equals(s)) return r;
14
            r++;
15
        }
16
        return -1;
17
    }
18
 
19
    private void permute(char[] a, int k) {
20
        if (k == a.length) { perms.add(new String(a)); return; }
21
        for (int i = k; i < a.length; i++) {
22
            swap(a, k, i);
23
            permute(a, k + 1);
24
            swap(a, k, i);
25
        }
26
    }
27
 
28
    private void swap(char[] a, int i, int j) { char t = a[i]; a[i] = a[j]; a[j] = t; }
29
 
30
    public static void main(String[] args) {
31
        System.out.println(new BruteForceRank().rank("acb"));
32
    }
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n! · n log(n!)) timeO(n! · n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Not deduplicating — repeated characters inflate the rank.Explore edge cases

Pitfalls

Not deduplicating — repeated characters inflate the rank.
Returning a 0-based index — off by one from the expected 1-based rank.
Trying it for n beyond ~10 — n! permutations exhaust time and memory.

03.2

Approach 2 of 2 · Optimal

Factorial Counting with Duplicate Handling (Optimal)

TimeO(n² ) or O(n·Σ)SpaceO(Σ)

The intended answer. Derive it from the factorial number system and handle duplicates with the Π freq! division.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk left to right. At position i, every permutation that puts a character smaller than s[i] here (and is otherwise any arrangement of the rest) sorts before s. How many such arrangements are there?

2Hint 2Explore hint

If the remaining characters are all distinct, fixing one smaller character leaves (n-1-i)! arrangements. Sum (count of smaller chars to the right) × (n-1-i)! over all i, then add 1.

3Hint 3Explore hint

With duplicates, (n-1-i)! over-counts because swapping identical characters yields the same string. Divide by the product of factorials of the remaining character frequencies.

A · Core idea

The optimal solution counts the permutations smaller than s directly, treating the answer as a number written in the factorial base.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba"

Array state

i=0 'a'

smaller to right = 0 → 0 × 2! = 0

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Factorial Counting with Duplicate Handling (Optimal) — optimal

5 teaching notes

1
import java.math.BigInteger;
2
 
3
public class LexRank {
4
    public BigInteger rank(String s) {
5
        int n = s.length();
6
        BigInteger[] fact = new BigInteger[n + 1];
7
        fact[0] = BigInteger.ONE;
8
        // Precompute factorials as BigInteger so 21! and beyond don't overflow.
9
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i));
10
 
11
        int[] freq = new int[256];
12
        for (int i = 0; i < n; i++) freq[s.charAt(i)]++;
13
 
14
        BigInteger rank = BigInteger.ZERO;
15
        for (int i = 0; i < n; i++) {
16
            char c = s.charAt(i);
17
            long smaller = 0;
18
            // Count characters strictly smaller than s[i] still available in the
19
            // suffix.
20
            for (int ch = 0; ch < c; ch++) smaller += freq[ch];
21
 
22
            BigInteger denom = BigInteger.ONE;
23
            for (int ch = 0; ch < 256; ch++) denom = denom.multiply(fact[freq[ch]]);
24
 
25
            // block = smaller * (n-1-i)! / Pi freq! : permutations diverging here and going smaller
26
            BigInteger block = BigInteger.valueOf(smaller)
27
                .multiply(fact[n - 1 - i])
28
                .divide(denom);
29
            rank = rank.add(block);
30
 
31
            // Consume s[i]; the suffix multiset shrinks before the next position.
32
            freq[c]--;
33
        }
34
        // +1 converts the count-of-smaller into a 1-based rank.
35
        return rank.add(BigInteger.ONE);
36
    }
37
 
38
    public static void main(String[] args) {
39
        System.out.println(new LexRank().rank("aba"));
40
        System.out.println(new LexRank().rank("string"));
41
    }
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(n² ) or O(n·Σ) timeO(Σ) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7s = "a" — Single character → only permutation → rank 1.Explore edge cases

Edge cases handled

s = "a"Single character → only permutation → rank 1.
s = "cba"Largest permutation of {a,b,c} → rank 6 (= 3!).
s = "aaa"Only one distinct permutation → rank 1; duplicate division cancels everything.

Pitfalls

Counting smaller characters over the whole string instead of only the suffix.
Ignoring duplicates — without the Π freq! division you over-count and inflate the rank.
Using 64-bit factorials beyond 20! — silent overflow to wrong (often negative) values.
Forgetting the +1, returning a 0-based count instead of a rank.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.math.BigInteger; public class LexRank { public BigInteger rank(String s) { int n = s.length();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.math.BigInteger;

int[] freq = new int[256];
        for (int i = 0; i < n; i++) freq[s.charAt(i)]++;

BigInteger denom = BigInteger.ONE;
            for (int ch = 0; ch < 256; ch++) denom = denom.multiply(fact[freq[ch]]);

freq[c]--;
        }
        return rank.add(BigInteger.ONE);
    }

public static void main(String[] args) {
        System.out.println(new LexRank().rank("aba"));
        System.out.println(new LexRank().rank("string"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Smaller count over the whole string

Only characters still available (to the right) can validly sit at position i. Counting smaller characters that already appeared in the prefix double-counts and corrupts the rank.

Explore the code comparison

Don't write this

smaller = sum(1 for ch in s if ch < s[i])   # whole string — wrong

Write this instead

smaller = sum(freq[ch] for ch in range(ord(s[i])))  # only remaining suffix

Ignoring duplicate characters

(n-1-i)! counts arrangements that are identical when characters repeat. Without dividing by Π freq! the block over-counts and the rank comes out too large.

Explore the code comparison

Don't write this

block = smaller * factorial(n - 1 - i)            # over-counts duplicates

Write this instead

denom = 1
for f in freq:
    denom *= factorial(f)
block = smaller * factorial(n - 1 - i) // denom

64-bit factorial overflow

21! exceeds the 64-bit range, so for longer strings the factorial silently wraps and every block is wrong. Use big integers or modular arithmetic.

Explore the code comparison

Don't write this

long f = 1; for (int k = 2; k <= n; k++) f *= k; // overflows at 21!

Write this instead

BigInteger f = BigInteger.ONE;
for (int k = 2; k <= n; k++) f = f.multiply(BigInteger.valueOf(k));

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Factorial number system: count permutations that sort before each prefix

Code pattern to memorize

DISTINCT:   rank = 1 + Σ_i  smallerRight(i) * (n-1-i)!
WITH DUPLICATES: rank = 1 + Σ_i  smallerRight(i) * (n-1-i)! / Π_c (freq[c]!)
  where freq is the frequency of the suffix s[i..n-1], updated as you advance

Rules to remember

1Rank is 1-based — the smallest permutation has rank 1, so the final answer adds 1.
2smallerRight(i) counts characters strictly less than s[i] among positions i+1..n-1, not the whole string.
3Each smaller character fixes position i and frees (n-1-i)! arrangements of the rest — that's why the factorial appears.
4Duplicates: divide each block by Π freq[c]! over the current suffix multiset, or you over-count identical arrangements.
5Factorials explode — 21! overflows 64-bit. Use big integers, or compute the rank modulo a prime with modular inverses.

Use this pattern when

Rank / un-rank a permutation in lexicographic order
Map a permutation to/from an index (factorial number system)
Find the k-th permutation, or how many permutations precede a given one
Any 'position in dictionary of all rearrangements' question

Choose another pattern when

You only need the *next* permutation → next_permutation in-place swap, not full ranking
Alphabet/length tiny and you just need any one answer → brute force all permutations
Strings are not permutations of each other → ranking among permutations is undefined
You need rank among arbitrary strings of a length, not permutations → positional base-Σ counting instead

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

k-th Permutation Sequence (un-rank)
Coming soon
Invert the formula: peel off factorial-base digits of k−1 to pick each character in turn.
Next Permutation
Coming soon
If you only need the immediately following permutation, do the in-place pivot-swap-reverse in O(n).
Rank of a String mod p (large n)
Coming soon
Precompute factorials and modular inverses; replace division by Π freq! with multiplication by inverses.
Rank Among All Strings of Length n
Coming soon
Not a permutation problem — use positional base-Σ counting instead of factorials.

Same pattern

←

Count Distinct Substrings

Continue · Next problem

Longest Palindromic Substring — Manacher's Algorithm