You are given a string s
(0-indexed). You are asked to perform the following operation on s
until you get a sorted string:
- Find the largest index
i
such that1 <= i < s.length
ands[i] < s[i - 1]
. - Find the largest index
j
such thati <= j < s.length
ands[k] < s[i - 1]
for all the possible values ofk
in the range[i, j]
inclusive. - Swap the two characters at indices
i - 1
andj
. - Reverse the suffix starting at index
i
.
Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 109 + 7
.
Example 1:
Input: s = "cba" Output: 5 Explanation: The simulation goes as follows: Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab". Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca". Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac". Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb". Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".
Example 2:
Input: s = "aabaa" Output: 2 Explanation: The simulation goes as follows: Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now, s="aaaba". Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now, s="aaaab".
Example 3:
Input: s = "cdbea" Output: 63
Example 4:
Input: s = "leetcodeleetcodeleetcode" Output: 982157772
Constraints:
1 <= s.length <= 3000
s
consists only of lowercase English letters.
Solution: Math
Time complexity: O(26n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
constexpr int kMod = 1e9 + 7; int64_t powm(int64_t b, int64_t p) { int64_t ans = 1; while (p) { if (p & 1) ans = (ans * b) % kMod; b = (b * b) % kMod; p >>= 1; } return ans; } class Solution { public: int makeStringSorted(string s) { const int n = s.length(); vector<int64_t> fact(n + 1, 1); vector<int64_t> inv(n + 1, 1); for (int i = 1; i <= n; ++i) { fact[i] = (fact[i - 1] * i) % kMod; inv[i] = powm(fact[i], kMod - 2); } int64_t ans = 0; vector<int> freq(26); for (int i = n - 1; i >= 0; --i) { const int idx = s[i] - 'a'; ++freq[idx]; int64_t cur = accumulate(begin(freq), begin(freq) + idx, 0ll) * fact[n - i - 1] % kMod; for (int f : freq) cur = cur * inv[f] % kMod; ans = (ans + cur) % kMod; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment