Minimize the String by finding the shortest path from one end to another

Step by step Shortest Path from source node to destination node in a Binary Tree

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 -> C

Input: 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)

Python

#  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# 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));

Output

ABDZ

Time complexity: O(n²)
Auxiliary Space: O(n)

Greedy Approach with Character Position Tracking

This solution employs a greedy approach with character position tracking to efficiently minimize the string by finding the shortest path from one end to another. It utilizes an unordered map to store the position of each character encountered in the output string ‘ans’. Whenever the same character is encountered again, the string ‘ans’ is truncated from that index to the end, effectively eliminating redundant paths and minimizing the string length.

Approach:

Store the destination character in a variable.
Use an unordered map to track the position of each character encountered in the output string ‘ans’.
Traverse the given string ‘s’ character by character.
If the current character is the destination character, append it to ‘ans’ and return.
If the current character is not present in the map, append it to ‘ans’ and record its position.
If the current character is already present in the map, truncate ‘ans’ from the position of the repeated character to the end.
Return the minimized ‘ans’ string.

C++

#include <iostream>
#include <string>
#include <unordered_map>

std::string minimizeString(const std::string& s)
{
    int n = s.length();
    char last = s[n - 1]; // Destination character
    std::string ans = ""; // Output string
    std::unordered_map<char, int>
        mp; // Map to store character positions

    // Traverse the string 's'
    for (int i = 0; i < n; ++i) {
        // If destination character is reached, append to
        // 'ans' and return
        if (s[i] == last) {
            ans += s[i];
            return ans;
        }

        // Insert position of newly encountered character
        // into map
        if (mp.find(s[i]) == mp.end()) {
            ans += s[i];
            mp[s[i]] = i;
        }
        // If character is already encountered, truncate
        // 'ans' from repeated character position
        else {
            int pos = mp[s[i]];
            ans = ans.substr(0, pos + 1);
        }
    }

    return ans;
}

int main()
{
    std::string str1 = "ABDCEDZ";
    std::cout << minimizeString(str1)
              << std::endl; // Output: ABDZ
    return 0;
}

Java

import java.util.HashMap;

public class MinimizeString {

    public static String minimizeString(String s)
    {
        int n = s.length(); // Get the length of the string
        char last
            = s.charAt(n - 1); // Destination character
        StringBuilder ans
            = new StringBuilder(); // Output string using
                                   // StringBuilder
        HashMap<Character, Integer> mp
            = new HashMap<>(); // Map to store character
                               // positions

        // Traverse the string 's'
        for (int i = 0; i < n; i++) {
            // If destination character is reached, append
            // to 'ans' and return
            if (s.charAt(i) == last) {
                ans.append(s.charAt(i));
                return ans.toString();
            }

            // Insert position of newly encountered
            // character into map
            if (!mp.containsKey(s.charAt(i))) {
                ans.append(s.charAt(i));
                mp.put(s.charAt(i), i);
            }
            // If character is already encountered, truncate
            // 'ans' from repeated character position
            else {
                int pos = mp.get(s.charAt(i));
                ans.setLength(pos + 1);
            }
        }

        return ans.toString();
    }

    public static void main(String[] args)
    {
        // Example usage
        String str1 = "ABDCEDZ";
        System.out.println(
            minimizeString(str1)); // Output: ABDZ
    }
}

Python

def minimize_string(s):
    n = len(s)
    last = s[-1]  # Destination character
    ans = ""  # Output string
    mp = {}  # Map to store character positions

    # Traverse the string 's'
    for i in range(n):
        # If destination character is reached, append to 'ans' and return
        if s[i] == last:
            ans += s[i]
            return ans

        # Insert position of newly encountered character into map
        if s[i] not in mp:
            ans += s[i]
            mp[s[i]] = i
        # If character is already encountered, truncate 'ans' from repeated character position
        else:
            pos = mp[s[i]]
            ans = ans[:pos + 1]

    return ans


# Example usage
str1 = "ABDCEDZ"
print(minimize_string(str1))  # Output: ABDZ

JavaScript

function minimizeString(s) {
    const n = s.length; // Get the length of the string
    const last = s[n - 1]; // Destination character
    let ans = ''; // Output string
    const mp = new Map(); // Map to store character positions

    // Traverse the string 's'
    for (let i = 0; i < n; i++) {
        // If destination character is reached, append to 'ans' and return
        if (s[i] === last) {
            ans += s[i];
            return ans;
        }

        // Insert position of newly encountered character into map
        if (!mp.has(s[i])) {
            ans += s[i];
            mp.set(s[i], i);
        } else {
            // If character is already encountered, truncate 'ans' from repeated
            // character position
            const pos = mp.get(s[i]);
            ans = ans.slice(0, pos + 1);
        }
    }

    return ans;
}

// Example usage
const str1 = "ABDCEDZ";
console.log(minimizeString(str1)); // Output: ABDZ

Output

ABDZ

Time Complexity: O(n), where n is the length of the input string.

Auxiliary Complexity: O(n), where n is the length of the input string.

Tags:

#Hash #strings #DSA #Hash #Strings #Hash #Hash #Strings #Strings

Step by step Shortest Path from source node to destination node in a Binary Tree

Minimize the String by finding the shortest path from one end to another

Greedy Approach with Character Position Tracking

Contact Us