DELAPP - EDITORIAL

editorial
,
1

DELAPP: Editorial

Problem-code: DELAPP

Contest-Code: CSMH2021

Author: JAMI YASHWANTH

Editorialist: JAMI YASHWANTH

DIFFICULTY:

MEDIUM

PREREQUISITES:

binary search,data structures,greedy,hashing,string suffix structures,strings,two pointers

PROBLEM:

Jack and you are friends . One fine day Jack challenged you to solve a problem .
Jack gives a string s, and you can do two types of operations on it:

Delete the last character of the string.
Duplicate the string: s:=s+s, where + denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly k that can be obtained by doing these operations on string s.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

a is a prefix of b, but a≠b;
In the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

SOLUTION:

#include
using namespace std;
 #define int             long long int
 
#define ff              first
#define ss              second
#define pb              push_back
#define MOD             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<>x; while(x--)
#define endl            "\n"
#define timetaken cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<> n >> k;
    string s;
    cin >> s;
    int bestLen = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] > s[i % bestLen]) break;
        if (s[i] < s[i % bestLen]) bestLen = i + 1;
    }
 
    s = s.substr(0, bestLen);
    while (s.size() < k) s += s;
    s = s.substr(0, k);
    cout << s << endl;
}
int32_t main()
{
    zanj0();
    solve();
    timetaken;
    return 0;
}