Problem: Sorted Permutation Rank
Given a string, find the rank of the string amongst its permutations sorted lexicographically. Assume that no characters are repeated.
Input : 'acb' Output : 2 The order permutations with letters 'a', 'c', and 'b' : abc acb bac bca cab cba
The answer might not fit in an integer, so return your answer % 1000003.
Refer the problem Sorted Permutation Rank with Repeats. The approach & solution to the problem is exactly the same, except that we are not considering the frequency of character because, in this problem, characters are unique without repeat.
Time & Space Complexity
Time Complexity: O(N^2)
- For every index we are traversing the string, to find the number of character lesser than the current one.
Space Complexity: O(1)
- Apart from the space taken by our input array, we have taken the constant amount of space, independent of the size of the string.
Code in C++