Рубрики

Лексикографически наименьшая строка, образованная добавлением символа из первых K символов строки | Набор 2

Heap, Строки

Учитывая строку str, состоящую из строчных букв и целого числа K , вы можете выполнить следующие операции над str

  1. Инициализируйте пустую строку X = «» .
  2. Возьмите любой символ из первых K символов str и добавьте его в X.
  3. Удалить выбранного персонажа с ул .
  4. Повторите вышеуказанные шаги, пока в str.

Задача состоит в том, чтобы сгенерировать X таким образом, чтобы он был минимально лексикографически, а затем распечатать сгенерированную строку.

Примеры:

Input: str = “geek”, K = 2
Output: eegk
Operation 1: str = “gek”, X = “e”
Operation 2: str = “gk”, X = “ee”
Operation 3: str = “k”, X = “eeg”
Operation 4: str = “”, X = “eegk”

Input: str = “geeksforgeeks”, K = 5
Output: eefggeekkorss

Подход: чтобы получить лексикографически наименьшую строку, нам нужно брать минимальный символ из первых K символов каждый раз, когда мы выбираем символ из str . Для этого мы можем поместить первые K символов в priority_queue (min-heap), а затем выбрать наименьший символ и добавить его в X. Затем поместите следующий символ в строке str в приоритетную очередь и повторяйте процесс, пока не останется символов для обработки.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата лексикографически
// наименьшая необходимая строка

string getSmallestStr(string S, int K)

{

  

    // изначально пустая строка

    string X = "";

  

    // минимальная куча символов

    priority_queue<char, vector<char>, greater<char> > pq;

  

    // Длина строки

    int i, n = S.length();

  

    // К не может быть больше чем

    // размер строки

    K = min(K, n);

  

    // Сначала нажимаем первые K символов

    // в файл priority_queue

    for (i = 0; i < K; i++)

        pq.push(S[i]);

  

    // Пока есть символы для добавления

    while (!pq.empty()) {

  

        // Добавляем вершину priority_queue к X

        X += pq.top();

  

        // Удалить верхний элемент

        pq.pop();

  

        // Push только если я меньше

        // размер строки

        if (i < S.length())

            pq.push(S[i]);

  

        i++;

    }

  

    // Возвращаем сгенерированную строку

    return X;

}

  
// Код драйвера

int main()

{

    string S = "geeksforgeeks";

    int K = 5;

  

    cout << getSmallestStr(S, K);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.PriorityQueue;

  

class GFG 

{

  

    // Функция для возврата лексикографически

    // наименьшая необходимая строка

    static String getSmallestStr(String S, int K)

    {

  

        // изначально пустая строка

        String X = "";

  

        // минимальная куча символов

        PriorityQueue<Character> pq = new PriorityQueue<>();

  

        // Длина строки

        int i, n = S.length();

  

        // К не может быть больше чем

        // размер строки

        K = Math.min(K, n);

  

        // Сначала нажимаем первые K символов

        // в файл priority_queue

        for (i = 0; i < K; i++)

            pq.add(S.charAt(i));

  

        // Пока есть символы для добавления

        while (!pq.isEmpty()) 

        {

  

            // Добавляем вершину priority_queue к X

            X += pq.peek();

  

            // Удалить верхний элемент

            pq.remove();

  

            // Push только если я меньше

            // размер строки

            if (i < S.length())

                pq.add(S.charAt(i));

                  

            i++;

        }

  

        // Возвращаем сгенерированную строку

        return X;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        String S = "geeksforgeeks";

        int K = 5;

        System.out.println(getSmallestStr(S, K));

    }

}

  
// Этот код предоставлен
// sanjeev2552

Выход:

eefggeekkorss

Рекомендуемые посты:

Лексикографически наименьшая строка, образованная добавлением символа из первых K символов строки | Набор 2

0.00 (0%) 0 votes