Reemplazo de caracteres después de eliminar duplicados de una string

Dada una string. La tarea es reemplazar cada carácter de la string minimizada por un carácter presente en el índice ‘ IND ‘ de la string original. La string minimizada es la string obtenida al eliminar todos los duplicados de la string original manteniendo el mismo orden de los elementos.

IND para cualquier índice en la string minimizada se calcula como: 

IND = (cuadrado del valor ascii del carácter de string minimizado) % (longitud de la string original)

Ejemplos: 

Input : geeks
Output : sesg
Explanation :   minimized string = geks
                length of original string = 5         
                ascii value of g = 103
                IND for g = (103*103) % 5 = 4
                replacement character for g = s 
                character 's' present at index 4 of original string
Similarly,
replacement character for e = e 
replacement character for k = s 
replacement character for s = g 

Input : helloworld
Output : oeoeeoh

Enfoque: a
continuación se muestra el algoritmo paso a paso para la minimización de strings:  

    1. Initialize flagchar[26] = {0}
    2. for i=0 to str.length()-1
    3.     ch = str[i]
    4.     if flagchar[ch-97] == 0 then
    5.         mstr = mstr + ch
    6.         flagchar[ch-97] = 1
    7.     End if
    8. End of loop
    9. return mstr  // minimized string

Algoritmo para el reemplazo de caracteres: 

    1. Replace each character of minimized string as described
       in the problem statement and example
    2. Compute final string 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for character replacement
// after string minimization
#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize string
string minimize(string str)
{
    string mstr = " ";
    int l, i, flagchar[26] = { 0 };
    char ch;
 
    l = str.length();
 
    // duplicate characters are removed
    for (i = 0; i < str.length(); i++) {
        ch = str.at(i);
 
        // checks if character has previously occurred or not
        // if not then add it to the minimized string 'mstr'
        if (flagchar[ch - 97] == 0) {
            mstr = mstr + ch;
            flagchar[ch - 97] = 1;
        }
    }
 
    return mstr; // minimized string
}
 
// Utility function to print the
// minimized, replaced string
void replaceMinimizeUtil(string str)
{
    string minimizedStr, finalStr = "";
    int i, index, l;
    char ch;
    l = str.length();
 
    minimizedStr = minimize(str); // minimized string
 
    // Creating final string by replacing character
    for (i = 0; i < minimizedStr.length(); i++) {
        ch = minimizedStr.at(i);
 
        // index calculation
        index = (ch * ch) % l;
 
        finalStr = finalStr + str.at(index);
    }
 
    cout << "Final string: " << finalStr; // final string
}
 
// Driver program
int main()
{
    string str = "geeks";
 
    replaceMinimizeUtil(str);
 
    return 0;
}

// Java program for character replacement
// after String minimization
 
class GFG {
    // Function to minimize String
 
    static String minimize(String str)
    {
        String mstr = " ";
        int l, i, flagchar[] = new int[26];
        char ch;
 
        l = str.length();
 
        // duplicate characters are removed
        for (i = 0; i < str.length(); i++) {
            ch = str.charAt(i);
 
            // checks if character has previously occurred or not
            // if not then add it to the minimized String 'mstr'
            if (flagchar[ch - 97] == 0) {
                mstr = mstr + ch;
                flagchar[ch - 97] = 1;
            }
        }
 
        return mstr; // minimized String
    }
 
    // Utility function to print the
    // minimized, replaced String
    static void replaceMinimizeUtil(String str)
    {
        String minimizedStr, finalStr = "";
        int i, index, l;
        char ch;
        l = str.length();
 
        minimizedStr = minimize(str); // minimized String
 
        // Creating final String by replacing character
        for (i = 0; i < minimizedStr.length(); i++) {
            ch = minimizedStr.charAt(i);
 
            // index calculation
            index = (ch * ch) % l;
 
            finalStr = finalStr + str.charAt(index);
        }
        // final String
        System.out.println("Final String: " + finalStr);
    }
 
    // Driver program
    public static void main(String[] args)
    {
        String str = "geeks";
 
        replaceMinimizeUtil(str);
    }
}
// This code is contributed by Rajput-JI

# Python3 program for character
# replacement after string minimization
 
# Function to minimize string
def minimize(string):
  
    mstr = " "
    flagchar = [0] * 26 
    l = len(string)
     
    # Duplicate characters are removed
    for i in range(0, len(string)):
      
        ch = string[i]
         
        # checks if character has previously occurred or not
        # if not then add it to the minimized string 'mstr'
        if flagchar[ord(ch)-97] == 0:
          
            mstr = mstr + ch
            flagchar[ord(ch)-97] = 1
                  
    return mstr # minimized string
  
# Utility function to print the
# minimized, replaced string
def replaceMinimizeUtil(string):
  
    finalStr = ""
    l = len(string)
    minimizedStr = minimize(string) # minimized string
     
    # Creating final string by replacing character
    for i in range(0, len(minimizedStr)):
      
        ch = ord(minimizedStr[i])
         
        # index calculation
        index = (ch * ch) % l
        finalStr = finalStr + string[index]
     
    print("Final string:", finalStr) # final string
  
# Driver program
if __name__ == "__main__":
  
    string = "geeks"
    replaceMinimizeUtil(string)
 
# This code is contributed by Rituraj Jain

// C# program for character replacement
// after String minimization
using System;
 
class GFG {
 
    // Function to minimize String
    static String minimize(string str)
    {
        string mstr = " ";
        int l, i;
        int[] flagchar = new int[26];
        char ch;
 
        l = str.Length;
 
        // duplicate characters are removed
        for (i = 0; i < str.Length; i++) {
            ch = str[i];
 
            // checks if character has previously
            // occurred or not if not then add it
            // to the minimized String 'mstr'
            if (flagchar[ch - 97] == 0) {
                mstr = mstr + ch;
                flagchar[ch - 97] = 1;
            }
        }
 
        return mstr; // minimized String
    }
 
    // Utility function to print the
    // minimized, replaced String
    static void replaceMinimizeUtil(string str)
    {
        string minimizedStr, finalStr = "";
        int i, index, l;
        char ch;
        l = str.Length;
 
        minimizedStr = minimize(str); // minimized String
 
        // Creating final String by
        // replacing character
        for (i = 0; i < minimizedStr.Length; i++) {
            ch = minimizedStr[i];
 
            // index calculation
            index = (ch * ch) % l;
 
            finalStr = finalStr + str[index];
        }
 
        // final String
        Console.Write("Final String: " + finalStr);
    }
 
    // Driver Code
    public static void Main()
    {
        string str = "geeks";
 
        replaceMinimizeUtil(str);
    }
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program for character replacement
// after string minimization
 
// Function to minimize string
function minimize($str)
{
    $mstr = " ";
    $flagchar=array_fill(0, 26, 0);
 
    $l = strlen($str);
 
    // duplicate characters are removed
    for ($i = 0; $i < strlen($str); $i++)
    {
        $ch = $str[$i];
 
        // checks if character has previously occurred or not
        // if not then add it to the minimized string 'mstr'
        if ($flagchar[ord($ch) - 97] == 0)
        {
            $mstr .=$ch;
            $flagchar[ord($ch) - 97] = 1;
        }
    }
 
    return $mstr; // minimized string
}
 
// Utility function to print the
// minimized, replaced string
function replaceMinimizeUtil($str)
{
 
    $finalStr = "";
 
    $l = strlen($str);
 
    $minimizedStr = minimize($str); // minimized string
 
    // Creating final string by replacing character
    for ($i = 0; $i < strlen($minimizedStr); $i++)
    {
        $ch = $minimizedStr[$i];
 
        // index calculation
        $index = (ord($ch) * ord($ch)) % $l;
 
        $finalStr = $finalStr.$str[$index];
    }
 
    echo "Final string: ".$finalStr; // final string
}
 
// Driver code
$str = "geeks";
 
replaceMinimizeUtil($str);
 
 
// This code is contributed by mits
?>

<script>
 
// Javascript program for character replacement
// after String minimization
 
// Function to minimize String
function minimize(str)
{
    let mstr = " ";
    let l, i, flagchar = new Array(26);
     
    for(let i = 0; i < 26; i++)
    {
        flagchar[i] = 0;
    }
    let ch;
 
    l = str.length;
 
    // Duplicate characters are removed
    for(i = 0; i < str.length; i++)
    {
        ch = str[i];
         
        // Checks if character has previously
        // occurred or not if not then add it
        // to the minimized String 'mstr'
        if (flagchar[ch.charCodeAt(0) - 97] == 0)
        {
            mstr = mstr + ch;
            flagchar[ch.charCodeAt(0) - 97] = 1;
        }
    }
     
    // Minimized String
    return mstr;
}
 
// Utility function to print the
// minimized, replaced String
function replaceMinimizeUtil(str)
{
    let minimizedStr, finalStr = "";
    let i, index, l;
    let ch;
    l = str.length;
     
    // Minimized String
    minimizedStr = minimize(str);
 
    // Creating final String by replacing character
    for(i = 0; i < minimizedStr.length; i++)
    {
        ch = minimizedStr[i].charCodeAt(0);
 
        // Index calculation
        index = (ch * ch) % l;
 
        finalStr = finalStr + str[index];
    }
     
    // Final String
    document.write("Final String: " + finalStr);
}
 
// Driver code
let str = "geeks";
 
replaceMinimizeUtil(str);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Final string: ssesg

Complejidad de tiempo : O(n)

Este artículo es una contribución de Ayush Jauhari . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.