Given string str of size N, the task is to print the number of substrings formed after maximum possible partitions such that no two substrings have a common character.
Examples:
Input : str = “ababcbacadefegdehijhklij”
Output : 3
Explanation:
Partitioning at the index 8 and at 15 produces three substrings “ababcbaca”, “defegde” and “hijhklij” such that none of them have a common character. So, the maximum partitions is 3.
Input: str = “aaa”
Output: 1
Explanation:
Since, the string consists of a single character, no partition can be performed.
Approach:
- Find the last index of every unique character from the end of the string and store it in a map.
- Traverse the array from the index 0 up to the last index and make a separate variable to store the ending index of partition.
- Traverse for every variable in the string and check if the end of the partition, denoted by the index of str[i] stored in the map, is greater than the previous end. If so, update it.
- Check if the current variable exceeds the end of the partition. It means the first partition is found. Update the end of the partition to max(k, mp[str[i]]).
- Traverse the whole string and use a similar process to find the next partition and so on.
Below is the implementation of the above approach :
C++
// C++ program to find the // maximum number of // partitions possible such // that no two substrings // have common character #include using namespace std; // Function to calculate and return // the maximum number of partitions int maximum_partition(string str) { // r: Stores the maximum number // of partitions // k: Stores the ending index // of the partition int i = 0, j = 0, k = 0; int c = 0, r = 0; // Stores the last index // of every unique character // of the string unordered_map m; // Traverse the string and // store the last index // of every character for (i = str.length() - 1; i >= 0; i--) { if (m[str[i]] == 0) { m[str[i]] = i; } } i = 0; // Store the last index of the // first character from map k = m[str[i]]; for (i = 0; i < str.length(); i++) { if (i <= k) { c = c + 1; // Update K to find // the end of partition k = max(k, m[str[i]]); } // Otherwise, the end of // partition is found else { // Increment r r = r + 1; c = 1; // Update k for the // next partition k = max(k, m[str[i]]); } } // Add the last partition if (c != 0) { r = r + 1; } return r; } // Driver Program int main() { string str = "ababcbacadefegdehijhklij"; cout << maximum_partition(str); } |
Java
// Java program to find the // maximum number of // partitions possible such // that no two subStrings // have common character import java.util.*;class GFG{ // Function to calculate and return // the maximum number of partitions static int maximum_partition(String str) { // r: Stores the maximum number // of partitions // k: Stores the ending index // of the partition int i = 0, j = 0, k = 0; int c = 0, r = 0; // Stores the last index // of every unique character // of the String HashMap<Character, Integer> m = new HashMap<>(); // Traverse the String and // store the last index // of every character for (i = str.length() - 1; i >= 0; i--) { if (!m.containsKey(str.charAt(i))) { m.put(str.charAt(i), i); } } i = 0; // Store the last index of the // first character from map k = m.get(str.charAt(i)); for (i = 0; i < str.length(); i++) { if (i <= k) { c = c + 1; // Update K to find // the end of partition k = Math.max(k, m.get(str.charAt(i))); } // Otherwise, the end of // partition is found else { // Increment r r = r + 1; c = 1; // Update k for the // next partition k = Math.max(k, m.get(str.charAt(i))); } } // Add the last // partition if (c != 0) { r = r + 1; } return r; } // Driver codepublic static void main(String[] args) { String str = "ababcbacadefegdehijhklij"; System.out.print(maximum_partition(str)); } }// This code is contributed by Princi Singh |
Python 3
# Python3 program to find the# maximum number of# partitions possible such# that no two substrings# have common character# Function to calculate and return# the maximum number of partitionsdef maximum_partition(strr): # r: Stores the maximum number # of partitions # k: Stores the ending index # of the partition i = 0 j = 0 k = 0 c = 0 r = 0 # Stores the last index # of every unique character # of the string m = {} # Traverse the and # store the last index # of every character for i in range(len(strr) - 1, -1, -1): if (strr[i] not in m): m[strr[i]] = i i = 0 # Store the last index of the # first character from map k = m[strr[i]] for i in range(len(strr)): if (i <= k): c = c + 1 # Update K to find # the end of partition k = max(k, m[strr[i]]) # Otherwise, the end of # partition is found else: # Increment r r = r + 1 c = 1 # Update k for the # next partition k = max(k, m[strr[i]]) # Add the last partition if (c != 0): r = r + 1 return r# Driver Codeif __name__ == '__main__': strr = "ababcbacadefegdehijhklij" print(maximum_partition(strr))# This code is contributed by Mohit Kumar |
C#
// C# program to find the // maximum number of // partitions possible such // that no two subStrings // have common character using System;using System.Collections.Generic;class GFG{ // Function to calculate and return // the maximum number of partitions static int maximum_partition(String str) { // r: Stores the maximum number // of partitions // k: Stores the ending index // of the partition int i = 0, j = 0, k = 0; int c = 0, r = 0; // Stores the last index // of every unique character // of the String Dictionary<char, int> m = new Dictionary<char, int>(); // Traverse the String and // store the last index // of every character for (i = str.Length - 1; i >= 0; i--) { if (!m.ContainsKey(str[i])) { m.Add(str[i], i); } } i = 0; // Store the last index of the // first character from map k = m[str[i]]; for (i = 0; i < str.Length; i++) { if (i <= k) { c = c + 1; // Update K to find // the end of partition k = Math.Max(k, m[str[i]]); } // Otherwise, the end of // partition is found else { // Increment r r = r + 1; c = 1; // Update k for the // next partition k = Math.Max(k, m[str[i]]); } } // Add the last // partition if (c != 0) { r = r + 1; } return r; } // Driver codepublic static void Main(String[] args) { String str = "ababcbacadefegdehijhklij"; Console.Write(maximum_partition(str)); } }// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program to find the // maximum number of // partitions possible such // that no two substrings // have common character // Function to calculate and return // the maximum number of partitions function maximum_partition( str) { // r: Stores the maximum number // of partitions // k: Stores the ending index // of the partition var i = 0, j = 0, k = 0; var c = 0, r = 0; // Stores the last index // of every unique character // of the string var m = new Map(); // Traverse the string and // store the last index // of every character for (i = str.length - 1; i >= 0; i--) { if (!m.has(str[i])) { m.set(str[i],i); } } i = 0; // Store the last index of the // first character from map k = m.get(str[i]); for (i = 0; i < str.length; i++) { if (i <= k) { c = c + 1; // Update K to find // the end of partition k = Math.max(k, m.get(str[i])); } // Otherwise, the end of // partition is found else { // Increment r r = r + 1; c = 1; // Update k for the // next partition k = Math.max(k, m.get(str[i])); } } // Add the last partition if (c != 0) { r = r + 1; } return r; } // Driver Program var str = "ababcbacadefegdehijhklij"; document.write( maximum_partition(str)); </script> |
Output:
3
Time complexity: O(NlogN)
Auxiliary Space: O(N) for map m
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!
