Given a string S consisting of N lowercase English alphabets, and also given that a character C is called K-amazing, if every substring of length at least K contains this character C, the task is to find the minimum possible K such that there exists at least one K-amazing character.
Examples:
Input: S = “abcde”
Output: 3
Explanation:
Every, substring of length at least 3, has one K-amazing character, ‘c’: {“abc”, “bcd”, “cde”, “abcd”, “bcde”, “abcde”}.Input: S = “aaaa”
Output: 1
Explanation:
Every, substring of length at least 1, has one K-amazing character, ‘a’: {“a”, “aa”, “aaa”, “aaaa”}.
For Naive and Binary Search approach, refer Set 1
Approach: The naive approach can be optimized based on the observation that for a character ‘C‘ to exist in every substring of length K, the distance between positions of two consecutive ‘C‘ cannot exceed K. Follow the steps below to solve the problem:
- Initialize an integer variable, say ans as N, which will store the minimum size of the substring possible such that every substring of size ans has at least one K-amazing character.
- Insert the character ‘0‘ to the front and end of the string S.
- Iterate over the characters in the range [a, z] using the variable c and perform the following steps:
- Assign character c to S[0] and S[N+1].
- Initialize two variables, say prev as 0 and maxLen as 0, where prev will store the last index of the character c and maxLen will store the maximum distance between the positions of the two nearest c.
- Iterate over the range [1, N+1] using the variable i and perform the following steps:
- If S[i] = c, then modify the value of maxLen to max(maxLen, i – prev) and then assign i to prev.
- Now modify the value of ans to min(ans, max_len).
- Finally, after completing the above steps, print the value of ans obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum value of K// such that there exist atleast one K// amazing characterint MinimumLengthSubstring(string S, int N){ // Stores the answer int ans = N; // Update the string S S = "0" + S + "0"; // Iterate over the characters // in range [a, z] for (char c = 'a'; c <= 'z'; ++c) { // Stores the last index where // c appears int prev = 0; // Stores the maximum possible length int max_len = 0; // Update string S S[0] = c; S[N + 1] = c; // Iterate over characters of string // S for (int i = 1; i <= N + 1; ++i) { // If S[i] is equal to c if (S[i] == c) { // Stores the distance between // positions of two same c int len = i - prev; // Update max_len max_len = max(max_len, len); // Update the value of prev prev = i; } } // Update the value of ans ans = min(ans, max_len); } // Return the answer return ans;}// Driver Codeint main(){ // Given Input string S = "abcde"; int N = S.length(); // Function Call cout << MinimumLengthSubstring(S, N);} |
Java
import java.util.*;public class Main { // Function to find minimum value of K // such that there exist atleast one K // amazing character static int MinimumLengthSubstring(String S, int N) { // Stores the answer int ans = N; // Update the string S S = "0" + S + "0"; // Iterate over the characters // in range [a, z] for (char c = 'a'; c <= 'z'; ++c) { // Stores the last index where // c appears int prev = 0; // Stores the maximum possible length int max_len = 0; // Update string S S = c + S.substring(1, S.length() - 1) + c; // Iterate over characters of string // S for (int i = 1; i <= N + 1; ++i) { // If S[i] is equal to c if (S.charAt(i) == c) { // Stores the distance between // positions of two same c int len = i - prev; // Update max_len max_len = Math.max(max_len, len); // Update the value of prev prev = i; } } // Update the value of ans ans = Math.min(ans, max_len); } // Return the answer return ans; } // Driver Code public static void main(String[] args) { // Given Input String S = "abcde"; int N = S.length(); // Function Call System.out.println(MinimumLengthSubstring(S, N)); }}// This code is contributed by NarasingaNikhil |
Python3
# Python3 program for the above approach# Function to find minimum value of K# such that there exist atleast one K# amazing characterdef MinimumLengthSubstring(S, N): # Stores the answer ans = N # Update the S S = "0" + S + "0" S = [i for i in S] # Iterate over the characters # in range [a, z] for c in range(ord('a'), ord('z') + 1): # Stores the last index where # c appears prev = 0 # Stores the maximum possible length max_len = 0 # Update S S[0] = chr(c) S[N + 1] = chr(c) # Iterate over characters of string # S for i in range(1, N + 2): # If S[i] is equal to c if (S[i] == chr(c)): # Stores the distance between # positions of two same c len = i - prev # Update max_len max_len = max(max_len, len) # Update the value of prev prev = i # Update the value of ans ans = min(ans, max_len) # Return the answer return ans# Driver Codeif __name__ == '__main__': # Given Input S = "abcde" N = len(S) # Function Call print(MinimumLengthSubstring(S, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find minimum value of K// such that there exist atleast one K// amazing characterstatic int MinimumLengthSubstring(string S, int N){ // Stores the answer int ans = N; // Update the string S S = "0" + S + "0"; // Iterate over the characters // in range [a, z] for (char c = 'a'; c <= 'z'; ++c) { // Stores the last index where // c appears int prev = 0; // Stores the maximum possible length int max_len = 0; // Update string S S = S.Substring(0,0) + c + S.Substring(1); S = S.Substring(0, N+1) + c + S.Substring(N + 2); // Iterate over characters of string // S for (int i = 1; i <= N + 1; ++i) { // If S[i] is equal to c if (S[i] == c) { // Stores the distance between // positions of two same c int len = i - prev; // Update max_len max_len = Math.Max(max_len, len); // Update the value of prev prev = i; } } // Update the value of ans ans = Math.Min(ans, max_len); } // Return the answer return ans;}// Driver Codepublic static void Main(){ // Given Input string S = "abcde"; int N = S.Length; // Function Call Console.Write(MinimumLengthSubstring(S, N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
// JavaScript program for the above approach// Function to find minimum value of K// such that there exist atleast one K// amazing characterfunction MinimumLengthSubstring(S, N) { // Stores the answer let ans = N; // Update the string S S = "0" + S + "0"; S = S.split("") // Iterate over the characters // in range [a, z] for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); ++c) { // Stores the last index where // c appears let prev = 0; // Stores the maximum possible length let max_len = 0; // Update string S S[0] = String.fromCharCode(c); S[N + 1] = String.fromCharCode(c); // Iterate over characters of string // S for (let i = 1; i <= N + 1; ++i) { // If S[i] is equal to c if (S[i] == String.fromCharCode(c)) { // Stores the distance between // positions of two same c let len = i - prev; // Update max_len max_len = Math.max(max_len, len); // Update the value of prev prev = i; } } // Update the value of ans ans = Math.min(ans, max_len); } // Return the answer return ans;}// Driver Code// Given Inputlet S = "abcde";let N = S.length;// Function Callconsole.log(MinimumLengthSubstring(S, N)); |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
