Minimum length substring with each letter occurring both in uppercase and lowercase
Find the minimum length substring in the given string str such that, in the substring, each alphabet appears at least once in lower case and at least once in upper case.
Examples:
Input: S = “AaBbCc”
Output: Aa
Explanation: Possible substrings that has each alphabet in lowercase and uppercase are:
Aa
Bb
Cc
AaBb
BbCc
AaBbCcAmong these, the minimum length substrings are Aa, Bb and Cc. Hence any of them can be a possible answer.
Input: S = “Beginner”
Output: -1
Explanation: No such substring present.
Naive Approach: The most straightforward approach is to generate all possible substrings of the given string and check if there exists any substring satisfying the given conditions. Print the smallest of all such substrings.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use the concept of Sliding Window. Follow the steps below to solve the problem:
- Traverse the given string and store the characters whose only lowercase or uppercase form are present in the input string in a Map mp.
- Initialize two arrays to keep track of the lowercase and uppercase characters obtained so far.
- Now, traverse the string maintaining two pointers i and st (initialized with 0), where st will point to the start of the current substring and i will point to the current character.
- If the current character is in mp, neglect all the characters obtained so far and start from the next character and adjust the arrays accordingly.
- If the current character is not in mp, remove the extra characters from the beginning of the substring with the help of st pointer, such that the frequency of any character does not convert to 0 and adjust the arrays accordingly.
- Now, check whether the substring {S[st], ….., S[i]} is balanced or not. If balanced and i – st + 1 is smaller than the length of balanced substring obtained so far. Update the length and also store the start and end indices of the substring, i.e. st and i respectively.
- Repeat the steps till the end of the string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the current // string is balanced or not bool balanced( int small[], int caps[]) { // For every character, check if // there exists uppercase as well // as lowercase characters for ( int i = 0; i < 26; i++) { if (small[i] != 0 && (caps[i] == 0)) return 0; else if ((small[i] == 0) && (caps[i] != 0)) return 0; } return 1; } // Function to find smallest length substring // in the given string which is balanced void smallestBalancedSubstring(string s) { // Store frequency of // lowercase characters int small[26]; // Stores frequency of // uppercase characters int caps[26]; memset (small, 0, sizeof (small)); memset (caps, 0, sizeof (caps)); // Count frequency of characters for ( int i = 0; i < s.length(); i++) { if (s[i] >= 65 && s[i] <= 90) caps[s[i] - 'A' ]++; else small[s[i] - 'a' ]++; } // Mark those characters which // are not present in both // lowercase and uppercase unordered_map< char , int > mp; for ( int i = 0; i < 26; i++) { if (small[i] && !caps[i]) mp[ char (i + 'a' )] = 1; else if (caps[i] && !small[i]) mp[ char (i + 'A' )] = 1; } // Initialize the frequencies // back to 0 memset (small, 0, sizeof (small)); memset (caps, 0, sizeof (caps)); // Marks the start and // end of current substring int i = 0, st = 0; // Marks the start and end // of required substring int start = -1, end = -1; // Stores the length of // smallest balanced substring int minm = INT_MAX; while (i < s.length()) { if (mp[s[i]]) { // Remove all characters // obtained so far while (st < i) { if (s[st] >= 65 && s[st] <= 90) caps[s[st] - 'A' ]--; else small[s[st] - 'a' ]--; st++; } i += 1; st = i; } else { if (s[i] >= 65 && s[i] <= 90) caps[s[i] - 'A' ]++; else small[s[i] - 'a' ]++; // Remove extra characters from // front of the current substring while (1) { if (s[st] >= 65 && s[st] <= 90 && caps[s[st] - 'A' ] > 1) { caps[s[st] - 'A' ]--; st++; } else if (s[st] >= 97 && s[st] <= 122 && small[s[st] - 'a' ] > 1) { small[s[st] - 'a' ]--; st++; } else break ; } // If substring (st, i) is balanced if (balanced(small, caps)) { if (minm > (i - st + 1)) { minm = i - st + 1; start = st; end = i; } } i += 1; } } // No balanced substring if (start == -1 || end == -1) cout << -1 << endl; // Store answer string else { string ans = "" ; for ( int i = start; i <= end; i++) ans += s[i]; cout << ans << endl; } } // Driver Code int main() { // Given string string s = "azABaabba" ; smallestBalancedSubstring(s); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to check if the current // string is balanced or not static boolean balanced( int small[], int caps[]) { // For every character, check if // there exists uppercase as well // as lowercase characters for ( int i = 0 ; i < 26 ; i++) { if (small[i] != 0 && (caps[i] == 0 )) return false ; else if ((small[i] == 0 ) && (caps[i] != 0 )) return false ; } return true ; } // Function to find smallest length substring // in the given string which is balanced static void smallestBalancedSubstring(String s) { // Store frequency of // lowercase characters int [] small = new int [ 26 ]; // Stores frequency of // uppercase characters int [] caps = new int [ 26 ]; Arrays.fill(small, 0 ); Arrays.fill(caps, 0 ); // Count frequency of characters for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) >= 65 && s.charAt(i) <= 90 ) caps[s.charAt(i) - 'A' ]++; else small[s.charAt(i) - 'a' ]++; } // Mark those characters which // are not present in both // lowercase and uppercase Map<Character, Integer> mp = new HashMap<Character, Integer>(); for ( int i = 0 ; i < 26 ; i++) { if (small[i] != 0 && caps[i] == 0 ) mp.put(( char )(i + 'a' ), 1 ); else if (caps[i] != 0 && small[i] == 0 ) mp.put(( char )(i + 'A' ), 1 ); // mp[char(i + 'A')] = 1; } // Initialize the frequencies // back to 0 Arrays.fill(small, 0 ); Arrays.fill(caps, 0 ); // Marks the start and // end of current substring int i = 0 , st = 0 ; // Marks the start and end // of required substring int start = - 1 , end = - 1 ; // Stores the length of // smallest balanced substring int minm = Integer.MAX_VALUE; while (i < s.length()) { if (mp.get(s.charAt(i)) != null ) { // Remove all characters // obtained so far while (st < i) { if (s.charAt(st) >= 65 && s.charAt(st) <= 90 ) caps[s.charAt(st) - 'A' ]--; else small[s.charAt(st) - 'a' ]--; st++; } i += 1 ; st = i; } else { if (s.charAt(i) >= 65 && s.charAt(i) <= 90 ) caps[s.charAt(i) - 'A' ]++; else small[s.charAt(i) - 'a' ]++; // Remove extra characters from // front of the current substring while ( true ) { if (s.charAt(st) >= 65 && s.charAt(st) <= 90 && caps[s.charAt(st) - 'A' ] > 1 ) { caps[s.charAt(st) - 'A' ]--; st++; } else if (s.charAt(st) >= 97 && s.charAt(st) <= 122 && small[s.charAt(st) - 'a' ] > 1 ) { small[s.charAt(st) - 'a' ]--; st++; } else break ; } // If substring (st, i) is balanced if (balanced(small, caps)) { if (minm > (i - st + 1 )) { minm = i - st + 1 ; start = st; end = i; } } i += 1 ; } } // No balanced substring if (start == - 1 || end == - 1 ) System.out.println(- 1 ); // Store answer string else { String ans = "" ; for ( int j = start; j <= end; j++) ans += s.charAt(j); System.out.println(ans); } } // Driver Code public static void main(String[] args) { // Given string String s = "azABaabba" ; smallestBalancedSubstring(s); } } // This code is contributed by Dharanendra L V |
Python3
# python 3 program for the above approach import sys # Function to check if the current # string is balanced or not def balanced(small, caps): # For every character, check if # there exists uppercase as well # as lowercase characters for i in range ( 26 ): if (small[i] ! = 0 and (caps[i] = = 0 )): return 0 elif ((small[i] = = 0 ) and (caps[i] ! = 0 )): return 0 return 1 # Function to find smallest length substring # in the given string which is balanced def smallestBalancedSubstring(s): # Store frequency of # lowercase characters small = [ 0 for i in range ( 26 )] # Stores frequency of # uppercase characters caps = [ 0 for i in range ( 26 )] # Count frequency of characters for i in range ( len (s)): if ( ord (s[i]) > = 65 and ord (s[i]) < = 90 ): caps[ ord (s[i]) - 65 ] + = 1 else : small[ ord (s[i]) - 97 ] + = 1 # Mark those characters which # are not present in both # lowercase and uppercase mp = {} for i in range ( 26 ): if (small[i] and caps[i] = = 0 ): mp[ chr (i + 97 )] = 1 elif (caps[i] and small[i] = = 0 ): mp[ chr (i + 65 )] = 1 # Initialize the frequencies # back to 0 for i in range ( len (small)): small[i] = 0 caps[i] = 0 # Marks the start and # end of current substring i = 0 st = 0 # Marks the start and end # of required substring start = - 1 end = - 1 # Stores the length of # smallest balanced substring minm = sys.maxsize while (i < len (s)): if (s[i] in mp): # Remove all characters # obtained so far while (st < i): if ( ord (s[st]) > = 65 and ord (s[st]) < = 90 ): caps[ ord (s[st]) - 65 ] - = 1 else : small[ ord (s[st]) - 97 ] - = 1 st + = 1 i + = 1 st = i else : if ( ord (s[i]) > = 65 and ord (s[i]) < = 90 ): caps[ ord (s[i]) - 65 ] + = 1 else : small[ ord (s[i] ) - 97 ] + = 1 # Remove extra characters from # front of the current substring while ( 1 ): if ( ord (s[st]) > = 65 and ord (s[st])< = 90 and caps[ ord (s[st]) - 65 ] > 1 ): caps[ ord (s[st]) - 65 ] - = 1 st + = 1 elif ( ord (s[st]) > = 97 and ord (s[st]) < = 122 and small[ ord (s[st]) - 97 ] > 1 ): small[ ord (s[st]) - 97 ] - = 1 st + = 1 else : break # If substring (st, i) is balanced if (balanced(small, caps)): if (minm > (i - st + 1 )): minm = i - st + 1 start = st end = i i + = 1 # No balanced substring if (start = = - 1 or end = = - 1 ): print ( - 1 ) # Store answer string else : ans = "" for i in range (start,end + 1 , 1 ): ans + = s[i] print (ans) # Driver Code if __name__ = = '__main__' : # Given string s = "azABaabba" smallestBalancedSubstring(s) # This code is contributed by bgangwar59. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { public const int MaxValue = 2147483647; // Function to check if the current // string is balanced or not static bool balanced( int []small, int []caps) { // For every character, check if // there exists uppercase as well // as lowercase characters for ( int i = 0; i < 26; i++) { if (small[i] != 0 && (caps[i] == 0)) return false ; else if ((small[i] == 0) && (caps[i] != 0)) return false ; } return true ; } // Function to find smallest length substring // in the given string which is balanced static void smallestBalancedSubstring( string s) { // Store frequency of // lowercase characters int [] small = new int [26]; int i; // Stores frequency of // uppercase characters int [] caps = new int [26]; Array.Clear(small, 0, small.Length); Array.Clear(caps, 0, caps.Length); // Count frequency of characters for (i = 0; i < s.Length; i++) { if (s[i] >= 65 && s[i] <= 90) caps[( int )s[i] - 65]++; else small[( int )s[i]- 97]++; } // Mark those characters which // are not present in both // lowercase and uppercase Dictionary< char , int > mp = new Dictionary< char , int >(); for (i = 0; i < 26; i++) { if (small[i] != 0 && caps[i] == 0){ mp[( char )(i+97)] = 1; } else if (caps[i] != 0 && small[i] == 0) mp[( char )(i+65)] = 1; // mp[char(i + 'A')] = 1; } // Initialize the frequencies // back to 0 Array.Clear(small, 0, small.Length); Array.Clear(caps, 0, caps.Length); // Marks the start and // end of current substring i = 0; int st = 0; // Marks the start and end // of required substring int start = -1, end = -1; // Stores the length of // smallest balanced substring int minm = MaxValue; while (i < s.Length) { if (mp.ContainsKey(s[i])) { // Remove all characters // obtained so far while (st < i) { if (( int )s[st] >= 65 && ( int )s[st] <= 90) caps[( int )s[st] - 65]--; else small[( int )s[st] - 97]--; st++; } i += 1; st = i; } else { if (( int )s[i] >= 65 && ( int )s[i] <= 90) caps[( int )s[i] - 65]++; else small[( int )s[i] - 97]++; // Remove extra characters from // front of the current substring while ( true ) { if (( int )s[st] >= 65 && ( int )s[st] <= 90 && caps[( int )s[st] - 65] > 1) { caps[( int )s[st] - 65]--; st++; } else if (( int )s[st] >= 97 && ( int )s[st] <= 122 && small[( int )s[st] - 97] > 1) { small[( int )s[st] - 97]--; st++; } else break ; } // If substring (st, i) is balanced if (balanced(small, caps)) { if (minm > (i - st + 1)) { minm = i - st + 1; start = st; end = i; } } i += 1; } } // No balanced substring if (start == -1 || end == -1) Console.WriteLine(-1); // Store answer string else { string ans = "" ; for ( int j = start; j <= end; j++) ans += s[j]; Console.WriteLine(ans); } } // Driver Code public static void Main() { // Given string string s = "azABaabba" ; smallestBalancedSubstring(s); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript program for the above approach let MaxValue = 2147483647; // Function to check if the current // string is balanced or not function balanced(small, caps) { // For every character, check if // there exists uppercase as well // as lowercase characters for (let i = 0; i < 26; i++) { if (small[i] != 0 && (caps[i] == 0)) return false ; else if ((small[i] == 0) && (caps[i] != 0)) return false ; } return true ; } // Function to find smallest length substring // in the given string which is balanced function smallestBalancedSubstring(s) { // Store frequency of // lowercase characters let small = new Array(26); let i; // Stores frequency of // uppercase characters let caps = new Array(26); small.fill(0); caps.fill(0); // Count frequency of characters for (i = 0; i < s.length; i++) { if (s[i].charCodeAt() >= 65 && s[i].charCodeAt() <= 90) caps[s[i].charCodeAt() - 65]++; else small[s[i].charCodeAt()- 97]++; } // Mark those characters which // are not present in both // lowercase and uppercase let mp = new Map(); for (i = 0; i < 26; i++) { if (small[i] != 0 && caps[i] == 0){ mp.set(String.fromCharCode(i+97), 1); } else if (caps[i] != 0 && small[i] == 0) mp.set(String.fromCharCode(i+65), 1); // mp[char(i + 'A')] = 1; } // Initialize the frequencies // back to 0 small.fill(0); caps.fill(0); // Marks the start and // end of current substring i = 0; let st = 0; // Marks the start and end // of required substring let start = -1, end = -1; // Stores the length of // smallest balanced substring let minm = MaxValue; while (i < s.length) { if (mp.has(s[i])) { // Remove all characters // obtained so far while (st < i) { if (s[st].charCodeAt() >= 65 && s[st].charCodeAt() <= 90) caps[s[st].charCodeAt() - 65]--; else small[s[st].charCodeAt() - 97]--; st++; } i += 1; st = i; } else { if (s[i].charCodeAt() >= 65 && s[i].charCodeAt() <= 90) caps[s[i].charCodeAt() - 65]++; else small[s[i].charCodeAt() - 97]++; // Remove extra characters from // front of the current substring while ( true ) { if (s[st].charCodeAt() >= 65 && s[st].charCodeAt() <= 90 && caps[s[st].charCodeAt() - 65] > 1) { caps[s[st].charCodeAt() - 65]--; st++; } else if (s[st].charCodeAt() >= 97 && s[st].charCodeAt() <= 122 && small[s[st].charCodeAt() - 97] > 1) { small[s[st].charCodeAt() - 97]--; st++; } else break ; } // If substring (st, i) is balanced if (balanced(small, caps)) { if (minm > (i - st + 1)) { minm = i - st + 1; start = st; end = i; } } i += 1; } } // No balanced substring if (start == -1 || end == -1) document.write(-1 + "</br>" ); // Store answer string else { let ans = "" ; for (let j = start; j <= end; j++) ans += s[j]; document.write(ans + "</br>" ); } } // Given string let s = "azABaabba" ; smallestBalancedSubstring(s); // This code is contributed by decode2207. </script> |
ABaab
Time Complexity: O(N)
Auxiliary Space: O(N)