字符串字典序排列排名：O(n)解法中计数数组构建的疑问

Hey there! I totally get where you're coming from—those O(n²) solutions feel straightforward, but that optimized approach with the count array can feel like a black box at first. Let's break down exactly how to build and use that count array to cut down the complexity.

First, let's recap why the O(n²) approach is slow: every time you fix a character in the string, you have to scan all remaining characters to count how many are smaller than it. That repeated scanning adds up to O(n²) time. The count array eliminates this repeated work by precomputing (and dynamically updating) the number of smaller characters available at each step.

Step 1: Precompute the Frequency Array #

First, we start by counting how many times each character appears in the original string. For example, if we're working with lowercase English letters, we can use a freq array of size 26, where freq[i] represents the number of times the character 'a' + i appears in the string.

This takes O(n) time—just loop through the string once and increment the corresponding index in freq.

Step 2: Build the Initial Count Array #

The count array is a prefix sum array derived from freq. For each character index i, count[i] equals the total number of characters in the string that are smaller than 'a' + i. In other words:

count[i] = sum(freq[0] + freq[1] + ... + freq[i-1])

To build this, you can loop from index 1 to the end of the character set, accumulating the sum as you go. For 26 lowercase letters, this is O(1) constant time (since 26 is fixed). For larger character sets, it's O(k) where k is the size of the character set.

Example for "bac" #

• Original string: "b", "a", "c"
• freq array: [1, 1, 1, 0, ..., 0] (index 0 = 'a', 1 = 'b', 2 = 'c')
• count array: [0, 1, 2, 2, ..., 2] (count[1] = freq[0] = 1, count[2] = freq[0]+freq[1] = 2)

Step 3: Use and Update the Count Array as You Process the String #

Now, as we iterate through each character in the string, we do two key things:

1. Calculate the number of smaller permutations: For the current character curr (converted to its index curr_idx), count[curr_idx] tells us how many characters smaller than curr are still available. Multiply this by (n - i - 1)! (where i is the current position, and n is the string length) and add this to the total number of permutations that come before our string.
2. Update the arrays to reflect used characters:
   • Decrement freq[curr_idx] by 1 (since we've used one instance of this character).
   • For all indices j > curr_idx, decrement count[j] by 1 (because one fewer smaller character exists for all larger characters now). For small character sets like 26 letters, this is a quick constant-time loop. For larger sets, we can use a Fenwick Tree (Binary Indexed Tree) or Segment Tree to handle updates and queries in O(log k) time, keeping the overall complexity efficient.

Continuing the "bac" Example #

• First character 'b' (index 1):
  • count[1] = 1 → 1 smaller character ('a') available. Multiply by 2! = 2 → add 2 to the total (total so far: 2).
  • Update freq[1] to 0, then decrement count[2...25] by 1. Now count[2] = 1.
• Second character 'a' (index 0):
  • count[0] = 0 → no smaller characters available. Multiply by 1! = 1 → add 0 (total remains 2).
  • Update freq[0] to 0, decrement count[1...25] by 1. Now count[2] = 0.
• Third character 'c': No remaining characters to process.

Finally, add 1 to the total (since we counted permutations that come before our string) → 2 + 1 = 3, which is the correct rank of "bac" (the third permutation in order: abc, acb, bac...).

Why This Is O(n) (or Near-O(n)) #

For small fixed character sets (like lowercase letters), all the array updates are constant time. The initial frequency and count array builds are O(n) and O(1) respectively, and processing each character is O(1) → overall O(n) time. For larger character sets, using a Fenwick Tree brings it to O(n log k), which is still way faster than O(n²) for large n.

内容的提问来源于stack exchange，提问作者Yash