# Minimum value of K such that each substring of size K has the given character

Given a string of lowercase letters S a character c. The task is to find minimum K such that every substring of length K contains the given character c. If there is no such K possible, return -1.Examples:Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Input: S = “abdegb”, ch = ‘b’Output: 4 Explanation:Consider the value of K as 4. Now, every substring of size K(= 4) are {“abde”, “bdeg”, “degb” } has the character ch(= b’).Input: S = “abfge”, ch = ‘m’Output : -1Naive Approach: The simplest approach to solve the given problem is to iterate for all possible sizes of substrings over the range [1, N] and check which minimum value of K satisfies the given criteria. If there doesn’t exist any such value of K, then print “-1”.Time Complexity: O(N4)Auxiliary Space: O(N)Efficient Approach: The above approach can also be optimized by using an observation that the minimum value of K is equal to the maximum difference between the consecutive occurrences of the given character ch as for every substring of size K there must have at least 1 character as ch. Follow the steps below to solve the given problem:Initialize a variable, say maxDifference as -1 that store the resultant value of K.Initialize a variable, say previous as 0 that store the previous occurrence of the character ch in the string S.Traverse the given string S using the variable i and if the current character is ch then update the value of maxDifference to the maximum of maxDifference and (i – previous) and the value of previous to i.After completing the above steps, print the value of maxDifference as the result.Below is the implementation of the above approach:C++#include using namespace std; int findK(string s, char c){ int n = s.length(); int diff; int max = 0; int prev = 0; for (int i = 0; i < n; i++) { if (s[i] == c) { diff = i - prev; prev = i; if (diff > max) { max = diff; } } } if (max == 0) return -1; return max;} int main(){ string S = “abdegb”; char ch = ‘b’; cout