StrIIRec | Topcoder Archive

Problem Statement

For a given string S of length n an inversion is a pair of integers (i, j) such that 0 <= i < j <= n-1 and S[i] > S[j]. (That is, the character at 0-based index i is greater than the character at 0-based index j.) For example, the string "abcab" has 3 inversions: (1, 3), (2, 3), and (2, 4).

Given are ints n and minInv, and a String minStr. We will consider all strings that are permutations of the first n lowercase English letters. That is, these strings have length n and contain each of the first n letters exactly once. Out of these strings, return the lexicographically smallest string R with the following two properties:

The number of inversions in R is at least minInv.
The string R is not lexicographically smaller than minStr.

If there is no such string, return an empty String instead.

Definition

Class:: StrIIRec
Method:: recovstr
Parameters:: int, int, String
Returns:: String
Method signature:: String recovstr(int n, int minInv, String minStr)
(be sure your method is public)

Notes

A String A is lexicographically smaller than a String B if A is a prefix of B or A contains a smaller character at the first position where the Strings differ.

Constraints

n will be between 1 and 20, inclusive.
minInv will be between 0 and n*(n-1)/2, inclusive.
minStr will contain between 1 and n characters, inclusive.
Each character in minStr will be one of the first n lowercase Latin letters.
All characters in minStr will be unique.

Examples

```
2
```
```
1
```
```
"ab"
```
```
Returns: "ba"
```
You must find the lexicographically smallest String that has at least 1 inversion and is not lexicographically smaller than "ab".
```
9
```
```
1
```
```
"efcdgab"
```
```
Returns: "efcdgabhi"
```
```
11
```
```
55
```
```
"debgikjfc"
```
```
Returns: "kjihgfedcba"
```
"kjihgfedcba" is the only String that has at least 55 inversions.
```
15
```
```
0
```
```
"e"
```
```
Returns: "eabcdfghijklmno"
```
```
9
```
```
20
```
```
"fcdebiha"
```
```
Returns: "fcdehigba"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.