Student Sequence :
Difficulty Level : Hard
Submissions : 51
Asked In :
Marks :10
: 1 | : 1
Before the prayer assembly begins, the students of different classes stand randomly in a single line. Often they become noisy. To maintain silence during the prayer assembly, the teacher tells them to stand in a particular sequence. The sequence is such that there are at least D students of other classes standing between students of the same class.
Write an algorithm to output the final sequence in which the students will stand. If no such sequence is possible, then output $$$-1$$$. If more than one sequence is possible, then output the lexicographically smallest string.
The first line of the input consists of a string $$$S$$$ $$$( 1 \le |S| \le 10^{5})$$$, representing the initial sequence in which the students stand.
The second line consists of an integer count $$$( 1 \le D \le 1000)$$$, representing the minimum number of students that stand between students of the same class.
Print the string representing the final sequence in which at least D students of other classes stand between students of the same class. Print $$$'-1'$$$ if it is impossible. If more than one sequence is possible, then output the lexicographically smallest string.
ddgdghghh 2
dghdghdgh
aaaaa 1
aaaaa
