Create a string with unique characters from the given N substrings
Last Updated :
23 Jul, 2025
Given an array arr[] containing N substrings consisting of lowercase English letters, the task is to return the minimum length string that contains all given parts as a substring. All characters in this new answer string should be distinct. If there are multiple strings with the following property present, you have to print the string with minimum length.
Examples:
Input: N = 3, arr[] = {"bcd", "ab", "cdef"}
Output: "abcdef"
Explanation:
- abcdef contains "bcd" from [1-3] index (0-based indexing)
- abcdef contains "ab" from [0-2]
- abcdef contains "cdef" from [2-5]
It can be proven that "abcdef" is the smallest string consisting of the given 3 substring fragments from input.
Input: N = 3, arr[]= {"dfghj", "ghjkl", "asdfg"];
Output: "asdfghjkl"
Explanation:
- asdfghjkl contains "dfghj" from [2-6] index (0-based indexing)
- asdfghjkl contains "ghjkl" from [4-8]
- asdfghjkl contains "asdfg" from [0-4]
It can be proven that "asdfghjkl " is the smallest string consisting of the given 3 substring fragments from input.
Approach: Implement the below idea to solve the problem:
- While traversing a string, if a character in left and right exists we will be storing this, information in the left[] and right[] array. If an element of a substring does not have a left element,
this means that it's the first element. We will be marking these elements as -1(indicating the start of a substring). - Finally, print the final answer. We will be starting with the character having a - 1 value in the left[] array because it's the start of the string and will gonna print its right element from the right[] array, now this right element is the new element and now we will be finding it's the right element from right[] array the same way until we reach -2 (as right) for an element, which indicates the end of the string.
Follow the steps to solve the above idea:
- Create two arrays left[] and right[] having size = 26 (a to z)
- Initialize each value for left[] and right[] = -2 (indicating the following characters has no left and right elements yet)
- Iterate over each substring given in the input array
- if it's the first character mark it's left = -1 (indicating the start of a substring)
- else if, it's left == -2 (does not exist yet) update it with the left character if it exists in the current substring
- update the right[] value by accessing s[i+1]th character of the current substring if it exists.
- To print the final result find out the index containing -2 in the left[] array
- print this element and update current = right[current]
- repeat until right != -2
Below is the code to implement the approach:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to create string containing
// all substrings of array arr[]
void formedString(int n, vector<string>& arr)
{
// Defining left and right array to
// store the left and right element
// for each character (a to z)
vector<int> left(26), right(26);
// Initializing left and right values
// for each character = -2 (indicating
// the following characters has no left
// and right elements yet)
for (int i = 0; i < 26; i++)
left[i] = right[i] = -2;
for (string s : arr) {
// Iterating over each substring s
// given in the array
for (int j = 0; j < s.size(); j++) {
// Finding the character index
// to store
int t = s[j] - 'a';
// If it's the first character
// of substring (means left
// does not exist)
if (j > 0) {
int t1 = s[j - 1] - 'a';
left[t] = t1;
}
else if (left[t] == -2)
left[t] = -1;
// If right element exists for
// jth character find it and
// store in right[t]
if (j < s.size() - 1) {
int t1 = s[j + 1] - 'a';
right[t] = t1;
}
}
}
// Code to output the final string
int j;
// Looping over all characters from
// (a to z) to find out the first
// index (having left = -1)
for (int i = 0; i < 26; i++)
if (left[i] == -1) {
// If 1st index is found print
// it and update j = right[j]
// and repeat until -2 is
// encountered -2 indicates
// the end
int j = i;
while (j != -2) {
// Converting the integer
// value into character
cout << (char)(j + 97);
j = right[j];
}
}
}
// Driver code
int main()
{
int n = 3;
vector<string> arr = { "dfghj", "ghjkl", "asdfg" };
// Function call
formedString(n, arr);
}
// Java code for the above approach:
import java.io.*;
import java.util.*;
class GFG {
// Function to create string containing
// all substrings of array arr[]
static void formedString(int n, String arr[])
{
// Defining left and right array to
// store the left and right element
// for each character (a to z)
int[] left = new int[26];
int[] right = new int[26];
// Initializing left and right values
// for each character = -2 (indicating
// the following characters has no left
// and right elements yet)
for (int i = 0; i < 26; i++)
left[i] = right[i] = -2;
for (String s : arr) {
// Iterating over each substring s
// given in the array
for (int j = 0; j < s.length(); j++) {
// Finding the character index
// to store
int t = s.charAt(j) - 'a';
// If it's the first character
// of substring (means left
// does not exist)
if (j > 0) {
int t1 = s.charAt(j - 1) - 'a';
left[t] = t1;
}
else if (left[t] == -2)
left[t] = -1;
// If right element exists for
// jth character find it and
// store in right[t]
if (j < s.length() - 1) {
int t1 = s.charAt(j + 1) - 'a';
right[t] = t1;
}
}
}
// Code to output the final string
int j;
// Looping over all characters from
// (a to z) to find out the first
// index (having left = -1)
for (int i = 0; i < 26; i++)
if (left[i] == -1) {
// If 1st index is found print
// it and update j = right[j]
// and repeat until -2 is
// encountered -2 indicates
// the end
j = i;
while (j != -2) {
// Converting the integer
// value into character
System.out.print((char)(j + 97));
j = right[j];
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 3;
String[] arr = { "dfghj", "ghjkl", "asdfg" };
// Function Call
formedString(n, arr);
}
}
# Python3 code for the above approach
# Function to create string containing
# all substrings of array arr[]
def formedstring(n, arr):
# Defining left and right array to
# store the left and right element
# for each character (a to z)
left = [-2 for i in range(26)]
right = [-2 for i in range(26)]
for s in arr:
# Iterating over each substring s
# given in the array
for j in range(len(s)):
# Find the character index to store
t = ord(s[j]) - ord('a')
# If it is the first character
# of substring (means left does not exist)
if j > 0:
t1 = ord(s[j - 1]) - ord('a')
left[t] = t1
elif left[t] == -2:
left[t] = -1
# If right element exists for jth character
# find it and store in right[t]
if j < len(s) - 1:
t1 = ord(s[j + 1]) - ord('a')
right[t] = t1
# Code to output the final string
j = None
# Looping over all characters from
# (a to z) to find out the first
# index (having left = -1)
for i in range(26):
if left[i] == -1:
# If 1st index is found print
# it and update j = right[j]
# and repeat until -2 is
# encountered -2 indicates the end
j = i
while j != -2:
# Converting the integer
# value into character
print(chr(j + 97), end="")
j = right[j]
# Driver code
if __name__ == "__main__":
n = 3
arr = ["dfghj", "ghjkl", "asdfg"]
# Function call
formedstring(n, arr)
#This code is contributed by nikhilsainiofficial546
// C# code for the above approach:
using System;
public class GFG{
// Function to create string containing
// all substrings of array arr[]
static void formedString(int n, string[] arr)
{
// Defining left and right array to
// store the left and right element
// for each character (a to z)
int[] left = new int[26];
int[] right = new int[26];
// Initializing left and right values
// for each character = -2 (indicating
// the following characters has no left
// and right elements yet)
for (int i = 0; i < 26; i++)
left[i] = right[i] = -2;
foreach (string s in arr) {
// Iterating over each substring s
// given in the array
for (int k = 0; k < s.Length;k++) {
// Finding the character index
// to store
int t = s[k] - 'a';
// If it's the first character
// of substring (means left
// does not exist)
if (k > 0) {
int t1 = s[k - 1] - 'a';
left[t] = t1;
}
else if (left[t] == -2)
left[t] = -1;
// If right element exists for
// jth character find it and
// store in right[t]
if (k < s.Length - 1) {
int t1 = s[k + 1] - 'a';
right[t] = t1;
}
}
}
// Code to output the final string
int j;
// Looping over all characters from
// (a to z) to find out the first
// index (having left = -1)
for (int i = 0; i < 26; i++)
if (left[i] == -1) {
// If 1st index is found print
// it and update j = right[j]
// and repeat until -2 is
// encountered -2 indicates
// the end
j = i;
while (j != -2) {
// Converting the integer
// value into character
Console.Write((char)(j + 97));
j = right[j];
}
}
}
// Driver code
static public void Main (){
int n = 3;
String[] arr = { "dfghj", "ghjkl", "asdfg" };
// Function Call
formedString(n, arr);
}
}
function formedString(n, arr) {
// Defining left and right array to
// store the left and right element
// for each character (a to z)
let left = Array(26).fill(-2);
let right = Array(26).fill(-2);
arr.forEach((s) => {
// Iterating over each substring s
// given in the array
for (let j = 0; j < s.length; j++) {
// Find the character index to store
let t = s.charCodeAt(j) - 'a'.charCodeAt(0);
// If it is the first character
// of substring (means left does not exist)
if (j > 0) {
let t1 = s.charCodeAt(j - 1) - 'a'.charCodeAt(0);
left[t] = t1;
} else if (left[t] == -2) {
left[t] = -1;
}
// If right element exists for jth character
// find it and store in right[t]
if (j < s.length - 1) {
let t1 = s.charCodeAt(j + 1) - 'a'.charCodeAt(0);
right[t] = t1;
}
}
});
// Code to output the final string
let j = null;
// Looping over all characters from
// (a to z) to find out the first
// index (having left = -1)
for (let i = 0; i < 26; i++) {
if (left[i] == -1) {
// If 1st index is found print
// it and update j = right[j]
// and repeat until -2 is
// encountered -2 indicates the end
j = i;
while (j != -2) {
// Converting the integer
// value into character
process.stdout.write(String.fromCharCode(j + 97));
j = right[j];
}
}
}
}
// Driver code
if (require.main === module) {
let n = 3;
let arr = ["dfghj", "ghjkl", "asdfg"];
// Function call
formedString(n, arr);
}
Time Complexity: O(N*C), Where C is equal to the maximum size of a substring.
Auxiliary Space: O(1) (two extra arrays left[] and right[] of size 26 are used which is constant for all input sizes).
Related Articles:
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem