3720: Lexicographically Smallest Permutation Greater Than Target #181
Description
Problem Number
3720
Problem Title
Lexicographically Smallest Permutation Greater Than Target
LeetCode Link
https://leetcode.com/problems/lexicographically-smallest-permutation-greater-than-target
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
- Create a frequency map of string s, initialise ans as empty string
- Run a loop from i=0 to i =n-1
a. Try to match the first ith characters of s and target (0 to i-1 in 0 indexing)
b. for the ith (0 indexed) character of target, find the first character greater than it in the remaining frequency map
c. if no such character found continue
d. else for all indices from i +1 onwards till n-1, put all remaining chars of map in ascending order.
e. if ans is empty string, set ans as found string, else set ans as minimum between ans and found string - return ans
Intuition
Size of string is in [1,300]. Approach must be O(n^2) or O(n^2 logn).
When can a string be greater than another string of the same length?
if and only if for all characters at j in [0,i] s[j] = t[j]
and s[i+1]>t[i+1]
where i +1 < n (for proper indexing)
Solution in C++
class Solution {
public:
string lexGreaterPermutation(string s, string target) {
string ans ="";
int n = s.length();
map<char,int>mp;
for(auto&e:s)mp[e]++;
for(int i =0;i<n;i++)
{
map<char,int> m2=mp;
string res ="";
bool ip=1;
for(int j = 0;j<i;j++)
{
char e=target[j];
if(!m2.count(e))
{
ip=0;
break;
}
res+=e;
m2[e]--;
if(m2[e]==0)m2.erase(e);
}
if(ip)
{
char e = target[i];
auto it = m2.upper_bound(e);
if(it!=m2.end())
{
res+=it->first;
it->second--;
if(it->second==0)m2.erase(it);
}
else continue;
for(auto&e:m2)
{
while(e.second--)res+=e.first;
}
if(ans =="")ans=res;
else ans = min(ans,res);
}
}
return ans;
}
};