Рубрики

Переставьте строку так, чтобы все одинаковые символы стали на расстоянии

Дана строка и положительное целое число d. Некоторые символы могут повторяться в данной строке. Переставьте символы данной строки так, чтобы одни и те же символы находились на расстоянии d друг от друга. Обратите внимание, что может быть много возможных перестановок, вывод должен быть одной из возможных перестановок. Если такая договоренность невозможна, об этом также следует сообщить.
Ожидаемая сложность по времени составляет O (n), где n — длина входной строки.

Examples:
Input:  "abb", d = 2
Output: "bab"

Input:  "aacbbc", d = 3
Output: "abcabc"

Input: "geeksforgeeks", d = 3
Output: egkegkesfesor

Input:  "aaa",  d = 2
Output: Cannot be rearranged

Подсказка: размер алфавита можно считать постоянным (256) и можно использовать дополнительное пространство.

Решение: Идея состоит в том, чтобы подсчитать частоты всех символов и сначала рассмотреть наиболее часто встречающийся символ и расположить все его появления как можно ближе. После размещения наиболее часто встречающегося символа повторите тот же процесс для остальных символов.

1) Пусть заданная строка будет str, а размер строки будет n

2) Traverse str, сохраните все символы и их частоты в Max Heap MH. Значение частоты определяет порядок в MH, т. Е. Наиболее частый символ находится в корне MH.

3) Сделать все символы строки как '/ 0'.

4) Делайте следующее, пока MH не пусто.
… А ) Извлечь наиболее часто встречающийся персонаж. Пусть извлеченный символ равен x, а его частота равна f.
Б) Найти первую доступную позицию в str, т. Е. Найти первую '/ 0' в str.
… В ) Пусть первая позиция будет р. Заполните x в p, p + d, .. p + (f-1) d

Ниже приведены реализации C ++ и Python вышеупомянутого алгоритма.

C / C ++

// C ++ программа для перестановки строки так, чтобы все одинаково
// символы становятся как минимум на расстоянии d
#include <iostream>
#include <cstring>
#include <cstdlib>
#define MAX 256

using namespace std;

  
// Структура для хранения символа 'c' и его частоты 'f'
// во входной строке

struct charFreq {

    char c;

    int f;

};

  
// Вспомогательная функция для обмена двумя элементами charFreq.

void swap(charFreq *x, charFreq *y) {

    charFreq z = *x;

    *x = *y;

    *y = z;

}

  
// Вспомогательная функция для максимизации узла freq [i] кучи
// хранится в freq []

void maxHeapify(charFreq freq[], int i, int heap_size)

{

    int l = i*2 + 1;

    int r = i*2 + 2;

    int largest = i;

    if (l < heap_size && freq[l].f > freq[i].f)

        largest = l;

    if (r < heap_size && freq[r].f > freq[largest].f)

        largest = r;

    if (largest != i)

    {

        swap(&freq[i], &freq[largest]);

        maxHeapify(freq, largest, heap_size);

    }

}

  
// Утилита для преобразования массива freq [] в максимальную кучу

void buildHeap(charFreq freq[], int n)

{

    int i = (n - 1)/2;

    while (i >= 0)

    {

        maxHeapify(freq, i, n);

        i--;

    }

}

  
// Утилита для удаления максимального элемента или корня из максимальной кучи

charFreq extractMax(charFreq freq[], int heap_size)

{

    charFreq root = freq[0];

    if (heap_size > 1)

    {

        freq[0] = freq[heap_size-1];

        maxHeapify(freq, 0, heap_size-1);

    }

    return root;

}

  
// Основная функция, которая переставляет входную строку 'str' так, что
// два одинаковых символа становятся на расстоянии

void rearrange(char str[], int d)

{

    // Находим длину входной строки

    int n = strlen(str);

  

    // Создать массив для хранения всех символов и их

    // частоты в стр []

    charFreq freq[MAX] = {{0, 0}};

  

    int m = 0; // Для хранения количества различных символов в str []

  

    // Обходим входную строку и сохраняем частоты всех

    // символы в массиве freq [].

    for (int i = 0; i < n; i++)

    {        

        char x = str[i];

  

        // Если этот символ встречался в первый раз, увеличиваем m

        if (freq[x].c == 0)

            freq[x].c = x, m++;

  

        (freq[x].f)++;

        str[i] = '\0'// Это изменение используется позже

    }

  

    // Создать максимальную кучу всех персонажей

    buildHeap(freq, MAX);

  

    // Теперь по одному извлекаем все отдельные символы из максимальной кучи

    // и помещаем их обратно в str [] с ограничением расстояния d

    for (int i = 0; i < m; i++)

    {

        charFreq x = extractMax(freq, MAX-i);

  

        // Находим первую доступную позицию в str []

        int p = i;

        while (str[p] != '\0')

            p++;

  

        // Заполняем xc в p, p + d, p + 2d, .. p + (f-1) d

        for (int k = 0; k < x.f; k++)

        {

            // Если индекс выходит за рамки размера, строка не может

            // переставить.

            if (p + d*k >= n)

            {

                cout << "Cannot be rearranged";

                exit(0);

            }

            str[p + d*k] = x.c;

        }

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char str[] = "aabbcc";

    rearrange(str, 3);

    cout << str;

}

питон

// Python program to rearrange a string so that all same 

// characters become at least d distance away

MAX = 256

  
# Структура для хранения символа 'c' и его частоты 'f'
# во входной строке

class charFreq(object):

    def __init__(self,c,f):

        self.c = c

        self.f = f

  
# Утилита для обмена двумя элементами charFreq.

def swap(x, y):

    return y, x

  
# Полезная функция

def toList(string):

    t = []

    for x in string:

        t.append(x)

  

    return t

  
# Полезная функция

def toString(l):

    return ''.join(l)

  
# Сервисная функция для максимизации узла freq [i] кучи
# хранится в freq []

def maxHeapify(freq, i, heap_size):

    l = i*2 + 1

    r = i*2 + 2

    largest = i

    if l < heap_size and freq[l].f > freq[i].f:

        largest = l

    if r < heap_size and freq[r].f > freq[largest].f:

        largest = r

    if largest != i:

        freq[i], freq[largest] = swap(freq[i], freq[largest])

        maxHeapify(freq, largest, heap_size)

  
# Сервисная функция для преобразования массива freq [] в максимальную кучу

def buildHeap(freq, n):

    i = (n - 1)/2

    while i >= 0:

        maxHeapify(freq, i, n)

        i-=1

  
# Утилита для удаления максимального элемента или корня из максимальной кучи

def extractMax(freq, heap_size):

    root = freq[0]

    if heap_size > 1:

        freq[0] = freq[heap_size-1]

        maxHeapify(freq, 0, heap_size-1)

  

    return root

  
# Основная функция, которая переставляет входную строку 'str' так, что
# два одинаковых персонажа становятся на расстоянии

def rearrange(string, d):

    # Найти длину входной строки

    n = len(string)

  

    # Создать массив для хранения всех символов и их

    # частоты в стр []

    freq = []

    for x in xrange(MAX):

        freq.append(charFreq(0,0))

  

    m = 0

  

    # Пройдите входную строку и сохраните частоты всех

    # символов в массиве freq [].

    for i in xrange(n):

        x = ord(string[i])

  

        # Если этот символ встречался в первый раз, увеличьте m

        if freq[x].c == 0:

            freq[x].c = chr(x)

            m+=1

  

        freq[x].f+=1

        string[i] = '\0'

  

    # Постройте максимальную кучу всех персонажей

    buildHeap(freq, MAX)

  

    # Теперь по одному извлекаем все отдельные символы из максимальной кучи

    # и поместите их обратно в str [] с ограничением расстояния d

    for i in xrange(m):

        x = extractMax(freq, MAX-i)

  

        # Найти первую доступную позицию в str []

        p = i

        while string[p] != '\0':

            p+=1

  

        # Заполните xc в p, p + d, p + 2d, .. p + (f-1) d

        for k in xrange(x.f):

  

            # Если индекс выходит за рамки размера, строка не может

            # переставить.

            if p + d*k >= n:

                print "Cannot be rearranged"

                return

  

            string[p + d*k] = x.c

  

    return toString(string)

  
# Драйверная программа

string = "aabbcc"

print rearrange(toList(string), 3)

  
# Этот код предоставлен BHAVYA JAIN


Выход:

abcabc

Алгоритмическая парадигма: жадный алгоритм

Сложность времени: временная сложность вышеописанной реализации составляет O (n + mLog (MAX)). Здесь n — длина строки, m — количество различных символов в строке str [], а MAX — максимально возможные различные символы. MAX обычно 256 (константа) и m меньше, чем MAX. Таким образом, временную сложность можно рассматривать как O (n).

Больше анализа:
Приведенный выше код может быть оптимизирован для хранения только m символов в куче, мы сохранили его таким образом, чтобы сделать код простым. Таким образом, временная сложность может быть улучшена до O (n + mLogm). Это не имеет большого значения, поскольку MAX является константой.

Также вышеупомянутый алгоритм может быть реализован с использованием алгоритма сортировки O (mLogm). Первые шаги приведенного выше алгоритма остаются прежними. Вместо того, чтобы строить кучу, мы можем отсортировать массив freq [] по возрастанию частот, а затем рассмотреть все символы один за другим из отсортированного массива.

Вскоре мы расскажем о расширенной версии, в которой одинаковые символы должны быть перемещены на расстояние не менее d.

Эта статья предоставлена Химаншу Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Переставьте строку так, чтобы все одинаковые символы стали на расстоянии

0.00 (0%) 0 votes