Company: ConcertAI Software Engineering_30march
Difficulty: medium
Problem Statement You are given a lowercase English string s and a positive integer k . A string made up of lowercase English letters is considered balanced if the frequency of every character in the string is a multiple of k . Your task is to find the lexicographically smallest balanced string of length n that is lexicographically not smaller than the given string s . If it is impossible to construct such a string, output -1. A string x is said to be lexicographically smaller than a string y if one of the following conditions holds: x is a proper prefix of y , or at the first index where the two strings differ, the character in x appears earlier in the alphabet than the corresponding character in y . Example 1: Input: 4 2 abcd Output: acac Explanation: In this test case "acac" is greater than or equal to s, and each letter appears 2 or 0 times in it, so it is beautiful. Example 2: Input: 9 3 abaabaaaa Output: abaabaaab Explanation: In this test case each letter appears 0, 3, or 6 time