Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- /* IMPORTANT
- here memoization can be done by observing the variables that are changing:
- Memo(string, k) (for a particular number string, how many swaps available)
- unordered_map<string, unordered_set<int> > Memo
- memo will be able to store what all 'k' have been calculated for the string.
- eg - "1234" k = 2, "1234" k = 1 will be different states, as both params are variable.
- we can also store the return value ... FOR DP purpose
- unordered_map<pair<string, int>, long long int> dp
- dp will be able to store what is the max number that can be formed if we have the state (number, k)
- */
- void swap(string &number, int l, int r){
- char temp = number[l];
- number[l] = number[r];
- number[r] = temp;
- }
- void maxNumberAfterKswaps(int level, int k, string ans, string &number, long long &_max){
- //base case
- // largest number after ATMOST k swaps (not necessary to do exactly k, but not more than k), so no base condition such as (level >= number.size() && k == 0)
- if(level >= number.size()){
- if(!ans.empty()){
- long long int ansToLL = stoll(ans);
- if(ansToLL > _max){
- _max = ansToLL;
- }
- }
- return;
- }
- //every level has 2 options, either swap with any number available, or don't swap
- //swap if swap is available i.e. k > 0
- //this number got swapped, so available for further use in that branch
- if(k > 0){
- for(int i = level + 1; i < number.size(); i++){
- if(number[level] != number[i]){
- swap(number, level, i);
- maxNumberAfterKswaps(level + 1, k - 1, ans + number[level], number, _max);
- swap(number, level, i);
- }
- }
- }
- // don't swap
- maxNumberAfterKswaps(level + 1, k, ans + number[level], number, _max);
- }
- int main() {
- // your code goes here
- string number;
- int k;
- cin >> number;
- cin >> k;
- long long int _max = LLONG_MIN;
- maxNumberAfterKswaps(0, k, "", number, _max);
- cout << _max << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
