Given a string S, split the given string into as many substrings as possible such that each character from the given string appears in a single substring and print all these possible parts. The task is to print those substrings.
Examples:
Input: S = “ababcbacadefegdehijhklij”
Output:
ababcbaca defegde hijhklij
Explanation:
a, b, c are only present in the first string.
d, e, f, g are only present in the second string.
h, i, j, k, l are only present in the third string.
Input: S = “acbbcc”
Output:
a cbbcc
Explanation:
a are only present in the first string.
b, c are only present in the second string.
Approach: Follow the steps below to solve the problem:
- Store the last index of occurrence of all characters in the string.
- Since the string contains only lowercase letters, simply use an array of fixed size 26 to store the last indices of each character.
- Initialize an empty string ans = “” and iterate over the given string and follow the steps below:
- Add the current character to the string ans if the last position of the character is more than the current index and increase the length of the partition.
- If the last position of the current character is equal to the current index, then print the current string stored in ans and initialize ans to “” for storing the next partition 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 print all the substringsvoid print_substring(string s){ int n = s.size(); // Stores the substrings string str = ""; // Stores last index of // characters of string s vector<int> ans; if (n == 0) { cout << "-1"; return; } // Find the last position of // each character in the string vector<int> last_pos(26, -1); for (int i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s[i] - 'a'] == -1) { last_pos[s[i] - 'a'] = i; } } int minp = -1; // Iterate the given string for (int i = 0; i < n; ++i) { // Get the last index of s[i] int lp = last_pos[s[i] - 'a']; // Extend the current partition // characters last pos minp = max(minp, lp); // If the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Add the respective character first str += s[i]; // Store the partition's // len and reset variables cout << str << ' '; // Update the minp and str minp = -1; str = ""; } else { str += s[i]; } }}// Driver Codeint main(){ // Input string string S = "ababcbacadefegdehijhklij"; // Function call print_substring(S); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to print all the substrings public static void print_substring(String s) { int n = s.length(); // Stores the substrings String str = ""; // Stores last index of // characters of string s Vector<Integer> ans = new Vector<Integer>(); if (n == 0) { System.out.print("-1"); return; } // Find the last position of // each character in the string int[] last_pos = new int[26]; Arrays.fill(last_pos, -1); for (int i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s.charAt(i) - 'a'] == -1) { last_pos[s.charAt(i) - 'a'] = i; } } int minp = -1; // Iterate the given string for (int i = 0; i < n; ++i) { // Get the last index of s[i] int lp = last_pos[s.charAt(i) - 'a']; // Extend the current partition // characters last pos minp = Math.max(minp, lp); // If the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Add the respective character first str += s.charAt(i); // Store the partition's // len and reset variables System.out.print(str + ' '); // Update the minp and str minp = -1; str = ""; } else { str += s.charAt(i); } } } // Driver Code public static void main(String[] args) { // Input string String S = "ababcbacadefegdehijhklij"; // Function call print_substring(S); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach # Function to print all the substrings def print_substring(s): n = len(s) # Stores the substrings str = "" # Stores last index of # characters of string s ans = [] if (n == 0): print("-1") return # Find the last position of # each character in the string last_pos = [-1] * 26 for i in range(n - 1, -1, -1): # Update the last index if (last_pos[ord(s[i]) - ord('a')] == -1): last_pos[ord(s[i]) - ord('a')] = i minp = -1 # Iterate the given string for i in range(n): # Get the last index of s[i] lp = last_pos[ord(s[i]) - ord('a')] # Extend the current partition # characters last pos minp = max(minp, lp) # If the current pos of # character equals the min pos # then the end of partition if (i == minp): #Add the respective character to the string str += s[i] # Store the partition's # len and reset variables print(str, end = " ") # Update the minp and str minp = -1 str = "" else: str += s[i]# Driver Code# Input stringS = "ababcbacadefegdehijhklij"# Function callprint_substring(S)# This code is contributed by Shivam Singh |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function to print all the substrings public static void print_substring(String s) { int n = s.Length; // Stores the substrings String str = ""; // Stores last index of // characters of string s //List<int> ans = new List<int>(); if (n == 0) { Console.Write("-1"); return; } // Find the last position of // each character in the string int[] last_pos = new int[26]; for(int i = 0; i < 26; i++) last_pos[i] = -1; for(int i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s[i] - 'a'] == -1) { last_pos[s[i] - 'a'] = i; } } int minp = -1; // Iterate the given string for(int i = 0; i < n; ++i) { // Get the last index of s[i] int lp = last_pos[s[i] - 'a']; // Extend the current partition // characters last pos minp = Math.Max(minp, lp); // If the current pos of // character equals the min pos // then the end of partition if (i == minp) { //Add respective character to the string str += s[i]; // Store the partition's // len and reset variables Console.Write(str + ' '); // Update the minp and str minp = -1; str = ""; } else { str += s[i]; } } }// Driver Codepublic static void Main(String[] args){ // Input string String S = "ababcbacadefegdehijhklij"; // Function call print_substring(S);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// javascript program for the// above approach // Function to print all the substrings function print_substring(s) { let n = s.length; // Stores the substrings let str = ""; // Stores last index of // characters of string s let ans = []; if (n == 0) { document.write("-1"); return; } // Find the last position of // each character in the string let last_pos = Array(26).fill(-1); for (let i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s[i].charCodeAt() - 'a'.charCodeAt()] == -1) { last_pos[s[i].charCodeAt() - 'a'.charCodeAt()] = i; } } let minp = -1; // Iterate the given string for (let i = 0; i < n; ++i) { // Get the last index of s[i] let lp = last_pos[s[i].charCodeAt() - 'a'.charCodeAt()]; // Extend the current partition // characters last pos minp = Math.max(minp, lp); // If the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Add the respective character first str += s[i]; // Store the partition's // len and reset variables document.write(str + ' '); // Update the minp and str minp = -1; str = ""; } else { str += s[i]; } } } // Driver Code // Input string let S = "ababcbacadefegdehijhklij"; // Function call print_substring(S); // This code is contributed by avijitmondal998.</script> |
Output
ababcbaca defegde hijhklij
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
