Minimize length of Substrings containing at least one common Character
Given a string str, the task is to find the minimum length of substrings such that all the sub strings of that length from str contains at least one common character. If no such length can be obtained, print -1.
Example:
Input: str = “saad”
Output: 2
Explanation:
All the substrings of length two of a given string are {“sa”, “aa”, “ad”}.
Since ‘a’ is common among all the substring, the minimum possible length of substrings having at least one common character is 2.Input: str = “w3wiki”
Output: 7
Explanation:
All possible substrings of length 7 are as follows:
- geeksfo
- eeksfor
- eksforg
- ksforge
- sforgee
- forgeek
- orgeeks
Since all the substrings have a common character e, the minimum possible length of substrings having at least one common character is 7.
Approach: This problem can be solved easily by using the Binary search Technique. Follow the steps below to solve the problem:
- Initialize low as 1 and high as a length of the string str.
- Find mid between low and high.
- If there is a one common character in all the sub strings of given string, then update high as mid -1.
- If it is not the case, then Update low as a mid + 1.
- Repeat the above steps for all the 26 possible characters in the alphabet.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check and return if // substrings of length mid has a // common character a bool check(string& str, int mid, char a) { // Length of the string int n = str.size(); // Initialise the first // occurrence of character a int previous = -1, i; for (i = 0; i < n; ++i) { if (str[i] == a) { // Check that distance b/w // the current and previous // occurrence of character a // is less than or equal to mid if (i - previous > mid) { return false ; } previous = i; } } // If distance exceeds mid if (i - previous > mid) return false ; else return true ; } // Function to check for all the // alphabets, if substrings of // length mid have a character common bool possible(string& str, int mid) { // Check for all 26 alphabets for ( int i = 0; i < 26; ++i) { // Check that char i + a is // common in all the substrings // of length mid if (check(str, mid, i + 'a' )) return true ; } // If no characters is common return false ; } // Function to calculate and return // the minm length of substrings int findMinLength(string& str) { // Initialise low and high int low = 1, high = str.length(); // Perform binary search while (low <= high) { // Update mid int mid = (low + high) / 2; // Check if one common character is // present in the length of the mid if (possible(str, mid)) high = mid - 1; else low = mid + 1; } // Returns the minimum length // that contain one // common character return high + 1; } // Function to check if all // characters are distinct bool ifAllDistinct(string str) { set< char > s; for ( char c : str) { s.insert(c); } return s.size() == str.size(); } // Driver Code int main() { string str = "w3wiki" ; if (ifAllDistinct(str)) cout << -1 << endl; else cout << findMinLength(str); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to check and return if // subStrings of length mid has a // common character a static boolean check( char [] str, int mid, char a) { // Length of the String int n = str.length; // Initialise the first // occurrence of character a int previous = - 1 , i; for (i = 0 ; i < n; ++i) { if (str[i] == a) { // Check that distance b/w // the current and previous // occurrence of character a // is less than or equal to mid if (i - previous > mid) { return false ; } previous = i; } } // If distance exceeds mid if (i - previous > mid) return false ; else return true ; } // Function to check for all the // alphabets, if subStrings of // length mid have a character common static boolean possible( char [] str, int mid) { // Check for all 26 alphabets for ( int i = 0 ; i < 26 ; ++i) { // Check that char i + a is // common in all the subStrings // of length mid if (check(str, mid, ( char )(i + 'a' ))) return true ; } // If no characters is common return false ; } // Function to calculate and return // the minm length of subStrings static int findMinLength( char [] str) { // Initialise low and high int low = 1 , high = str.length; // Perform binary search while (low <= high) { // Update mid int mid = (low + high) / 2 ; // Check if one common character is // present in the length of the mid if (possible(str, mid)) high = mid - 1 ; else low = mid + 1 ; } // Returns the minimum length // that contain one // common character return high + 1 ; } // Function to check if all // characters are distinct static boolean ifAllDistinct(String str) { HashSet<Character> s = new HashSet<Character>(); for ( char c : str.toCharArray()) { s.add(c); } return s.size() == str.length(); } // Driver Code public static void main(String[] args) { String str = "w3wiki" ; if (ifAllDistinct(str)) System.out.print(- 1 + "\n" ); else System.out.print(findMinLength( str.toCharArray())); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement # the above approach # Function to check and return if # substrings of length mid has a # common character a def check(st, mid, a): # Length of the string n = len (st) # Initialise the first # occurrence of character a previous = - 1 for i in range (n): if (st[i] = = chr (a)): # Check that distance b/w # the current and previous # occurrence of character a # is less than or equal to mid if (i - previous > mid): return False previous = i # If distance exceeds mid if (i - previous > mid): return False else : return True # Function to check for all the # alphabets, if substrings of # length mid have a character common def possible(st, mid): # Check for all 26 alphabets for i in range ( 26 ): # Check that char i + a is # common in all the substrings # of length mid if (check(st, mid, i + ord ( 'a' ))): return True # If no characters is common return False # Function to calculate and return # the minm length of substrings def findMinLength(st): # Initialise low and high low = 1 high = len (st) # Perform binary search while (low < = high): # Update mid mid = (low + high) / / 2 # Check if one common character is # present in the length of the mid if (possible(st, mid)): high = mid - 1 else : low = mid + 1 # Returns the minimum length # that contain one # common character return high + 1 # Function to check if all # characters are distinct def ifAllDistinct( st): s = [] for c in st: s.append(c) return len ( set (s)) = = len (st) # Driver Code if __name__ = = "__main__" : st = "w3wiki" if (ifAllDistinct(st)): print ( "-1" ) else : print (findMinLength(st)) # This code is contributed by chitranayal |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to check and return if // subStrings of length mid has a // common character a static bool check( char [] str, int mid, char a) { // Length of the String int n = str.Length; // Initialise the first // occurrence of character a int previous = -1, i; for (i = 0; i < n; ++i) { if (str[i] == a) { // Check that distance b/w // the current and previous // occurrence of character a // is less than or equal to mid if (i - previous > mid) { return false ; } previous = i; } } // If distance exceeds mid if (i - previous > mid) return false ; else return true ; } // Function to check for all the // alphabets, if subStrings of // length mid have a character common static bool possible( char [] str, int mid) { // Check for all 26 alphabets for ( int i = 0; i < 26; ++i) { // Check that char i + a is // common in all the subStrings // of length mid if (check(str, mid, ( char )(i + 'a' ))) return true ; } // If no characters is common return false ; } // Function to calculate and return // the minm length of subStrings static int findMinLength( char [] str) { // Initialise low and high int low = 1, high = str.Length; // Perform binary search while (low <= high) { // Update mid int mid = (low + high) / 2; // Check if one common character is // present in the length of the mid if (possible(str, mid)) high = mid - 1; else low = mid + 1; } // Returns the minimum length // that contain one // common character return high + 1; } // Function to check if all // characters are distinct static bool ifAllDistinct(String str) { HashSet< char > s = new HashSet< char >(); foreach ( char c in str.ToCharArray()) { s.Add(c); } return s.Count == str.Length; } // Driver Code public static void Main(String[] args) { String str = "w3wiki" ; if (ifAllDistinct(str)) Console.Write(-1 + "\n" ); else Console.Write(findMinLength( str.ToCharArray())); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program to implement // the above approach // Function to check and return if // subStrings of length mid has a // common character a function check(str, mid, a) { // Length of the String var n = str.length; // Initialise the first // occurrence of character a var previous = -1, i; for (i = 0; i < n; ++i) { if (str[i] === a) { // Check that distance b/w // the current and previous // occurrence of character a // is less than or equal to mid if (i - previous > mid) { return false ; } previous = i; } } // If distance exceeds mid if (i - previous > mid) return false ; else return true ; } // Function to check for all the // alphabets, if subStrings of // length mid have a character common function possible(str, mid) { // Check for all 26 alphabets for ( var i = 0; i < 26; ++i) { // Check that char i + a is // common in all the subStrings // of length mid if (check(str, mid, String.fromCharCode( i + "a" .charCodeAt(0)))) return true ; } // If no characters is common return false ; } // Function to calculate and return // the minm length of subStrings function findMinLength(str) { // Initialise low and high var low = 1, high = str.length; // Perform binary search while (low <= high) { // Update mid var mid = parseInt((low + high) / 2); // Check if one common character is // present in the length of the mid if (possible(str, mid)) high = mid - 1; else low = mid + 1; } // Returns the minimum length // that contain one // common character return high + 1; } // Function to check if all // characters are distinct function ifAllDistinct(str) { var s = new Array(); var temp = str.split( "" ); for (const c of temp) { s.push(c); } var set = new Set(s); return set.size === str.length; } // Driver Code var str = "w3wiki" ; if (ifAllDistinct(str)) document.write(-1 + "<br>" ); else document.write( findMinLength(str.split( "" ))); // This code is contributed by rdtank </script> |
7
Time Complexity : O(26 * N * log(N))
Auxiliary Space: O(1)