Given two positive integers I and X and an array of strings arr[], the task is to sort the given array of strings on the basis of substrings starting from index I of size X.
Examples:
Input: I = 2, X = 2, arr[] = { “baqwer”, “zacaeaz”, “aaqzzaa”, “aacaap”, “abbatyo”, “bbbacztr”, “bbbdaaa” }
Output: abbatyo bbbacztr bbbdaaa aacaap zacaeaz baqwer aaqzzaa
Explanation:
All sub-strings starting from index I = 2 and of size x = 2 are {“qw”, “ca”, “qz”, “ca”, “ba”, “ba”, “bd”}.
Sorting them in lexicographical increasing order gives {“ba”, “ba”, “bd”, “ca”, “ca”, “qw”, “qz” }, then print the corresponding original string in this order.Input: I = 1, X = 3, arr[] = { “submit”, “source”, “skills”, “epidemic”, “ample”, “apple” }
Output: skills ample source epidemic apple submit
Approach: The idea is to create a substring of all the strings in the given array from index I of size X and keep the count of pair of a substring with the corresponding string in a map of pairs. After inserting in the map of pairs. After inserting, traverse the map and print 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 sort the given array// of strings based on substringvoid sortArray(vector<string> s, int l, int x){ // Map of pairs to sort vector // of strings map<pair<string, string>, int> mp; for (int i = 0; i < s.size(); i++) { // Create substring from index // 'l' and of size 'X' string part = s[i].substr(l, x); // Insert in Map mp[{ part, s[i] }] += 1; } // Print the sorted vector of strings for (auto it = mp.begin(); it != mp.end(); ++it) { // Traverse the number of time // a string is present for (int j = 0; j < it->second; j++) { // Print the string cout << it->first.second << ' '; } }}// Driver Codeint main(){ // Given array of strings vector<string> arr; arr = { "baqwer", "zacaeaz", "aaqzzaa", "aacaap", "abbatyo", "bbbacztr", "bbbdaaa" }; // Given I and X int I = 2, X = 2; // Function Call sortArray(arr, I, X); return 0;} |
Java
import java.util.*;public class Main { // Function to sort the given array // of strings based on substring static void sortArray(String[] s, int l, int x) { // Map of pairs to sort array of strings Map<String, Integer> mp = new TreeMap<>(); for (int i = 0; i < s.length; i++) { // Create substring from index 'l' and of size 'x' String part = s[i].substring(l, l + x); // Insert in Map if (mp.containsKey(part + s[i])) { mp.put(part + s[i], mp.get(part + s[i]) + 1); } else { mp.put(part + s[i], 1); } } // Print the sorted array of strings for (String key : mp.keySet()) { // Traverse the number of time a string is present for (int j = 0; j < mp.get(key); j++) { // Print the string System.out.print(key.substring(x) + " "); } } } // Driver Code public static void main(String[] args) { // Given array of strings String[] arr = { "baqwer", "zacaeaz", "aaqzzaa", "aacaap", "abbatyo", "bbbacztr", "bbbdaaa" }; // Given I and X int I = 2, X = 2; // Function Call sortArray(arr, I, X); }} |
Python3
# Python program for the above approach# Function to sort the given array# of strings based on substringdef sortArray(s, l, x): # Map of pairs to sort vector # of strings mp = {} for i in range(len(s)): # Create substring from index # 'l' and of size 'X' part = s[i][l:l+x] # Insert in Map if (part, s[i]) in mp: mp[(part, s[i])] += 1 else: mp[(part, s[i])] = 1 # Print the sorted vector of strings for key, value in sorted(mp.items()): # Traverse the number of time # a string is present for j in range(value): # Print the string print(key[1], end=" ")# Driver Codeif __name__ == "__main__": # Given array of strings arr = ["baqwer", "zacaeaz", "aaqzzaa", "aacaap", "abbatyo", "bbbacztr", "bbbdaaa"] # Given I and X I = 2 X = 2 # Function Call sortArray(arr, I, X) |
Javascript
// JavaScript code for the above approachconst sortArray = (s, l, x) => { // Map of pairs to sort array of strings let mp = new Map(); for (let i = 0; i < s.length; i++) { // Create substring from index 'l' and of size 'x' let part = s[i].substring(l, l + x); // Insert in Map if (!mp.has(part + s[i])) { mp.set(part + s[i], 1); } else { mp.set(part + s[i], mp.get(part + s[i]) + 1); } } // Print the sorted array of strings let sortedArray = Array.from(mp.keys()).sort(); for (let i = 0; i < sortedArray.length; i++) { // Traverse the number of time a string is present for (let j = 0; j < mp.get(sortedArray[i]); j++) { // Print the string console.log(sortedArray[i].substring(x)); } }};// Given array of stringslet arr = [ "baqwer", "zacaeaz", "aaqzzaa", "aacaap", "abbatyo", "bbbacztr", "bbbdaaa",];// Given I and Xlet I = 2, X = 2;// Function CallsortArray(arr, I, X); |
C#
// C# code for the approachusing System;using System.Collections.Generic;using System.Linq;class GFG { // Function to sort the given array // of strings based on substring static void SortArray(List<string> s, int l, int x) { // Map of pairs to sort vector // of strings Dictionary<Tuple<string, string>, int> mp = new Dictionary<Tuple<string, string>, int>(); for (int i = 0; i < s.Count; i++) { // Create substring from index 'l' and of size 'x' string part = s[i].Substring(l, x); // Insert in Map var key = new Tuple<string, string>(part, s[i]); if (mp.ContainsKey(key)) { mp[key]++; } else { mp[key] = 1; } } // Print the sorted vector of strings foreach (var item in mp.OrderBy(kvp => kvp.Key)) { // Traverse the number of times a string is present for (int j = 0; j < item.Value; j++) { // Print the string Console.Write(item.Key.Item2 + " "); } } } // Driver Code static void Main(string[] args) { // Given array of strings List<string> arr = new List<string> { "baqwer", "zacaeaz", "aaqzzaa", "aacaap", "abbatyo", "bbbacztr", "bbbdaaa" }; // Given I and X int I = 2, X = 2; // Function Call SortArray(arr, I, X); }} |
Output:
abbatyo bbbacztr bbbdaaa aacaap zacaeaz baqwer aaqzzaa
Time Complexity: O(N*log 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!
