Given a string str representing a direct connection between arr[i] and arr[i+1] in the given string, the task is to minimize the string by finding the shortest path from one end to another end.
Examples:
Input: str = “ABDCEDZ”
Output: ABDZ
Explanation: Here our starting point is A and our ending point is Z So the shortest path is A->B->D->Z. In input, the movement is A->B->D->C->E->D->Z but we can move directly from D->Z, no need to move from D->C->E->D->Z so the final output is A->B->D->Z.Input: str = “ABC”
Output: ABC
Explanation: here is the single path to move from A to C . A -> B -> CInput: str = “ADBDE”
Output: ADE
Explanation: Starting point is A and the Ending point is E, Here we can see D connected with W so no need to move A->D->B->D->E just move A->D->E.
Approach: Follow the approach below to understand the implementation:
In this approach we use unordered_map to store the position of the character in output ‘ans’ string, whenever we get the same character we minimize our string ‘ans’.
Follow the steps to solve the problem:
- Store the destination in a variable.
- Take an unordered_map to store every character and its indexes.
- If the current character is already present in the map means we have come to the same point again so erase our current answer string from that index to the last point.
- When we get our destination character stop there and return the answer string.
Below is the code for the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function which returns the minimized // string string minimizeString(string str) { int n = str.length(); // Last variable contains the // destination int last = str[n - 1]; string ans = "" ; // map to store the position of // character in our answer string unordered_map< char , int > mp; // Traverse the given string 'str' for ( int i = 0; i < n; i++) { // If we reach the destination // then return our 'ans' string // if find the destiny in middle // of string then no need to // traverse the whole string. if (str[i] == last) { ans += str[i]; return ans; } // Insert position of newly added // character into map if (mp.find(str[i]) == mp.end()) { ans += str[i]; mp[str[i]] = i; } // We get the same element again else { // Find the position of this // character in our 'ans' // string and just delete ans // string after that character // upto end. int pos = mp[str[i]]; ans = ans.substr(0, pos + 1); } } } // Drivers code int main() { string str = "ABDCEDZ" ; // Function Call cout << minimizeString(str); return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function which returns the minimized string public static String minimizeString(String str) { int n = str.length(); // Last variable contains the // destination int last = str.charAt(n - 1 ); StringBuilder ans = new StringBuilder(); // map to store the position of // character in our answer string Map<Character, Integer> mp = new HashMap<>(); // Traverse the given string 'str' for ( int i = 0 ; i < n; i++) { // If we reach the destination // then return our 'ans' string // if find the destiny in middle // of string then no need to // traverse the whole string. if (str.charAt(i) == last) { ans.append(str.charAt(i)); return ans.toString(); } // Insert position of newly added // character into map if (!mp.containsKey(str.charAt(i))) { ans.append(str.charAt(i)); mp.put(str.charAt(i), i); } // We get the same element again else { // Find the position of this // character in our 'ans' // string and just delete ans // string after that character // upto end. int pos = mp.get(str.charAt(i)); ans.delete(pos + 1 , ans.length()); } } return ans.toString(); } // Drivers code public static void main(String[] args) { String str = "ABDCEDZ" ; // Function Call System.out.println(minimizeString(str)); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code to implement the approach # Function which returns the minimized string def minimizeString(s): n = len (s) last = s[n - 1 ] # last variable contains the destination ans = "" mp = {} # map to store the position of character in our answer string # Traverse the given string 's' for i in range (n): # If we reach the destination # then return our 'ans' string # if find the destiny in middle # of string then no need to # traverse the whole string. if s[i] = = last: ans + = s[i] return ans # Insert position of newly added # character into map if s[i] not in mp: ans + = s[i] mp[s[i]] = i # We get the same element again else : # Find the position of this # character in our 'ans' # string and just delete ans # string after that character # upto end. pos = mp[s[i]] ans = ans[:pos + 1 ] return ans # Drivers code str = "ABDCEDZ" # Function Call print (minimizeString( str )) # This Code is Contributed by rutikbhosale |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class Program { // Function which returns the minimized string static string MinimizeString( string str) { int n = str.Length; // Last variable contains the destination int last = str[n - 1]; string ans = "" ; // map to store the position of character in our // answer string Dictionary< char , int > mp = new Dictionary< char , int >(); // Traverse the given string 'str' for ( int i = 0; i < n; i++) { // If we reach the destination // then return our 'ans' string // if find the destiny in middle // of string then no need to // traverse the whole string. if (str[i] == last) { ans += str[i]; return ans; } // Insert position of newly added // character into map if (!mp.ContainsKey(str[i])) { ans += str[i]; mp.Add(str[i], i); } // We get the same element again else { // Find the position of this // character in our 'ans' // string and just delete ans // string after that character // upto end. int pos = mp[str[i]]; ans = ans.Substring(0, pos + 1); } } return ans; } // Drivers code static void Main( string [] args) { string str = "ABDCEDZ" ; // Function Call Console.WriteLine(MinimizeString(str)); } } |
Javascript
// Javascript code to implement the approach // Function which returns the minimized // string function minimizeString(str) { const n = str.length; // Last variable contains the // destination const last = str[n - 1]; let ans = "" ; // map to store the position of // character in our answer string const mp = new Map(); // Traverse the given string 'str' for (let i = 0; i < n; i++) { // If we reach the destination // then return our 'ans' string // if find the destiny in middle // of string then no need to // traverse the whole string. if (str[i] === last) { ans += str[i]; return ans; } // Insert position of newly added // character into map if (!mp.has(str[i])) { ans += str[i]; mp.set(str[i], i); } // We get the same element again else { // Find the position of this // character in our 'ans' // string and just delete ans // string after that character // upto end. const pos = mp.get(str[i]); ans = ans.substr(0, pos + 1); } } return ans; } // Drivers code const str = "ABDCEDZ" ; // Function Call console.log(minimizeString(str)); |
ABDZ
Time complexity: O(n2)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!