construct string with repeat limit
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to find the
// largest lexicographical
// string with given constraints.
string getLargestString(string s,
ll k)
{
// vector containing frequency
// of each character.
vector<int> frequency_array(26, 0);
// assigning frequency to
for (int i = 0;
i < s.length(); i++) {
frequency_array[s[i] - 'a']++;
}
// empty string of string class type
string ans = "";
// loop to iterate over
// maximum priority first.
for (int i = 25; i >= 0;) {
// if frequency is greater than
// or equal to k.
if (frequency_array[i] > k) {
// temporary variable to operate
// in-place of k.
int temp = k;
string st(1, i + 'a');
while (temp > 0) {
// concatenating with the
// resultant string ans.
ans += st;
temp--;
}
frequency_array[i] -= k;
// handling k case by adjusting
// with just smaller priority
// element.
int j = i - 1;
while (frequency_array[j]
<= 0
&& j >= 0) {
j--;
}
// condition to verify if index
// j does have frequency
// greater than 0;
if (frequency_array[j] > 0
&& j >= 0) {
string str(1, j + 'a');
ans += str;
frequency_array[j] -= 1;
}
else {
// if no such element is found
// than string can not be
// processed further.
break;
}
}
// if frequency is greater than 0
// and less than k.
else if (frequency_array[i] > 0) {
// here we don't need to fix K
// consecutive element criteria.
int temp = frequency_array[i];
frequency_array[i] -= temp;
string st(1, i + 'a');
while (temp > 0) {
ans += st;
temp--;
}
}
// otherwise check for next
// possible element.
else {
i--;
}
}
return ans;
}
// Driver program
int main()
{
string S = "xxxxzza";
int k = 3;
cout << getLargestString(S, k)
<< endl;
return 0;
}