Рубрики

Наименьшая длина строки с повторной заменой двух различных смежных

Для заданной строки любой комбинации из трех букв «a», «b» и «c» найдите длину наименьшей строки, которую можно получить, повторно применяя следующую операцию:
Возьмите любые два соседних отличных символа и замените их третьим.

Примеры:

Input : cab
Output : 2
We can select any two adjacent letters, 
say 'ca' and transform it into 'b', this 
leaves us with string 'bb' of length two.
    
Input : bcab
Output : 1
Selecting 'bc' and transforming it to 'a' 
leaves us with 'aab'. We can then select
'ab' and transform it to 'c', giving 'ac'. 
This can further be transformed into 'b',
which is of length one.

Наивным способом сделать это было бы найти все возможные замены и повторять до тех пор, пока мы не найдем минимальную строку. Это займет экспоненциальное время.

Лемма : порядок букв не влияет на длину или значение минимальной строки.

Доказательство Индукцией
Базовый случай : возьмите строки 'ab' и 'ba', они оба уменьшают до 'c'

Индуктивная гипотеза : все строки длиной <= k сводятся к одной и той же строке, предполагая, что число вхождений каждой буквы в каждой строке одинаково.

Шаг индукции : возьмите две строки длиной k + 1, имеющие одинаковое количество вхождений каждой буквы. Найдите пару букв, которые находятся рядом
в обеих строках. Здесь возникают два случая:

  1. Нам удается найти такую пару писем. Затем мы можем заменить эти буквы третьей буквой, получив, таким образом, две строки длины k, имеющие одинаковые вхождения каждой буквы, которые по индуктивной гипотезе сводятся к одной и той же строке. то есть у нас есть 'abcacb' и 'accbba' и мы сокращаем 'ac' в обеих строках, таким образом, мы получаем 'abcbb' и 'bcbba'.
  2. Мы не можем найти такую пару. Это возникает, когда все буквы в строке одинаковы. В этом случае две строки сами по себе являются одинаковыми, то есть ccccccc и ccccccc.

Таким образом, по индукции мы доказали эту лемму.

Подход динамического программирования
Теперь мы можем разработать функцию с использованием динамического программирования для решения этой проблемы.

// C ++ программа для поиска наименьшей возможной длины
// строки только из трех символов
#include<bits/stdc++.h>

using namespace std;

  
// Программа для поиска длины сокращенной строки
// в строке из трех символов.
#define MAX_LEN 110

  
// Для сохранения результатов подзадач

int DP[MAX_LEN][MAX_LEN][MAX_LEN];

  
// Записанная функция находит результат рекурсивно.
// a, b и c являются счетчиками «a», «b» и
// 'c's in str

int length(int a, int b, int c)

{

    // Если эта подзадача уже оценена

    if (DP[a][b] != -1)

        return DP[a][b];

  

    // Если есть только один тип персонажа

    if (a == 0 && b == 0)

        return (DP[a][b] = c);

    if (a == 0 && c == 0)

        return (DP[a][b] = b);

    if (b == 0 && c == 0)

        return (DP[a][b] = a);

  

    // Если присутствуют только два типа символов

    if (a == 0)

        return (DP[a][b] =

                    length(a + 1, b - 1, c - 1));

    if (b == 0)

        return (DP[a][b] =

                    length(a - 1, b + 1, c - 1));

    if (c == 0)

        return (DP[a][b] =

                    length(a - 1, b - 1, c + 1));

  

    // Если присутствуют все типы символов.

    // Попробуйте объединить все пары.

    return (DP[a][b] =

                min(length(a - 1, b - 1, c + 1),

                    min(length(a - 1, b + 1, c - 1),

                        length(a + 1, b - 1, c - 1))));

}

  
// Возвращает наименьшую возможную длину с заданным
// операция разрешена.

int stringReduction(string str)

{

    int n = str.length();

  

    // Подсчет вхождений трех разных

    // символы 'a', 'b' и 'c' в строке

    int count[3] = {0};

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

        count[str[i]-'a']++;

  

    // Инициализируем записи DP [] [] как -1

    for (int i = 0; i <= count[0]; ++i)

        for (int j = 0; j < count[1]; ++j)

            for (int k = 0; k < count[2]; ++k)

                DP[i][j][k] = -1;

  

    return length(count[0], count[1], count[2]);

}

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

int main()

{

    string str = "abcbbaacb";

    cout << stringReduction(str);

    return 0;

}

Выход:

1

В худшем случае каждая буква присутствует в 1/3 всей строки. Это приводит к вспомогательному пространству = O (N 3 ) и временной сложности = O (N 3 )

Space Complexity = O(N^3)
Time Complexity = O(N^3)

Математический подход
Мы можем добиться большего успеха, используя три основных принципа:

  1. Если строка не может быть уменьшена далее, то все буквы в строке одинаковы.
  2. Длина минимальной строки либо <= 2, либо равна длине исходной строки, либо 2 <минимальная длина строки <исходная длина строки никогда не бывает истинной.
  3. Если каждая буква строки присутствует нечетное количество раз, то после одного шага сокращения все они должны присутствовать четное количество раз. Обратное также верно, то есть, если каждая буква строки присутствует четное количество раз, они должны присутствовать нечетное количество раз после одного шага сокращения.

Это может быть доказано следующим образом:

  1. Если присутствуют любые две разные буквы, мы можем выбрать их и еще больше уменьшить длину строки.
  2. Доказательство от противного:
    Предположим, у нас есть уменьшенная строка длины меньше, чем исходная строка. Например, «bbbbbbb». Тогда эта строка должна происходить из строки, подобной 'acbbbbbb', 'bbacbbbb' или любой другой подобной комбинации того же самого. В этом случае мы могли бы выбрать «bc» вместо «ac» и еще больше сократить.
  3. С рекурсивного шага выше мы увеличиваем одну букву на одну и уменьшаем две другие на одну. Таким образом, если бы у нас была комбинация как (нечетная, нечетная, нечетная), то она стала бы (нечетной + 1, нечетной — 1, нечетной — 1) или (четной, четной, четной). Реверс показан аналогичным образом.

Теперь мы можем объединить вышеуказанные принципы.
Если строка состоит из повторения одной и той же буквы, ее минимальная сокращенная строка сама по себе, а длина — длина строки.
Теперь другие возможные варианты — уменьшенная строка длиной в один или два символа. Теперь, если все символы присутствуют четное число раз или нечетное количество раз, единственный возможный ответ — 2, потому что (0, 2, 0) является (четным, четным, четным), в то время как (0, 1, 0) (четный, нечетный, четный), поэтому только 2 сохраняет эту четность.
В любом другом случае ответ становится 1.

C ++

// C ++ программа для поиска наименьшей возможной длины
// строки только из трех символов
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает наименьшую возможную длину с заданным
// операция разрешена.

int stringReduction(string str)

{

    int n = str.length();

  

    // Количество вхождений трех разных

    // символы 'a', 'b' и 'c' в строке

    int count[3] = {0};

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

        count[str[i]-'a']++;

  

    // Если все символы одинаковы.

    if (count[0] == n || count[1] == n ||

        count[2] == n)

        return n;

  

    // Если присутствуют все символы четного числа

    // раз или все присутствуют нечетное число

    // раз.

    if ((count[0] % 2) == (count[1] % 2) &&

        (count[1] % 2) == (count[2] % 2))

        return 2;

  

    // Ответ равен 1 для всех остальных случаев.

    return 1;

}

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

int main()

{

    string str = "abcbbaacb";

    cout << stringReduction(str);

    return 0;

}

Джава

// Java-программа для поиска минимально возможной длины
// строки только из трех символов

public class GFG {

  
// Возвращает наименьшую возможную длину с заданным
// операция разрешена.

    static int stringReduction(String str) {

        int n = str.length();

  

        // Количество вхождений трех разных

        // символы 'a', 'b' и 'c' в строке

        int count[] = new int[3];

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

            count[str.charAt(i) - 'a']++;

        }

  

        // Если все символы одинаковы.

        if (count[0] == n || count[1] == n

                || count[2] == n) {

            return n;

        }

  

        // Если присутствуют все символы четного числа

        // раз или все присутствуют нечетное число

        // раз.

        if ((count[0] % 2) == (count[1] % 2)

                && (count[1] % 2) == (count[2] % 2)) {

            return 2;

        }

  

        // Ответ равен 1 для всех остальных случаев.

        return 1;

    }

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

    public static void main(String[] args) {

        String str = "abcbbaacb";

        System.out.println(stringReduction(str));

    }

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

Python 3

# Программа Python 3 для поиска минимально возможного
# длина строки только из трех символов

  
# Возвращает наименьшую возможную длину
# с разрешенной операцией.

def stringReduction(str):

  

    n = len(str)

  

    # Количество появлений трех разных

    # символы 'a', 'b' и 'c' в строке

    count = [0] * 3

    for i in range(n):

        count[ord(str[i]) - ord('a')] += 1

  

    # Если все символы одинаковы.

    if (count[0] == n or count[1] == n or 

                         count[2] == n):

        return n

  

    # Если присутствуют все символы четного числа

    количество раз или все присутствуют нечетное число

    # раз.

    if ((count[0] % 2) == (count[1] % 2) and

        (count[1] % 2) == (count[2] % 2)):

        return 2

  

    # Ответ - 1 для всех остальных случаев.

    return 1

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

if __name__ == "__main__":

      

    str = "abcbbaacb"

    print(stringReduction(str))

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

C #

// C # программа для поиска наименьшей возможной длины
// строки только из трех символов

using System;

public class GFG { 

  
// Возвращает наименьшую возможную длину с заданным
// операция разрешена.

    static int stringReduction(String str) { 

        int n = str.Length; 

  

        // Количество вхождений трех разных

        // символы 'a', 'b' и 'c' в строке

        int []count = new int[3]; 

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

            count[str[i] - 'a']++; 

        

  

        // Если все символы одинаковы.

        if (count[0] == n || count[1] == n 

                || count[2] == n) { 

            return n; 

        

  

        // Если присутствуют все символы четного числа

        // раз или все присутствуют нечетное число

        // раз.

        if ((count[0] % 2) == (count[1] % 2) 

                && (count[1] % 2) == (count[2] % 2)) { 

            return 2; 

        

  

        // Ответ равен 1 для всех остальных случаев.

        return 1; 

    

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

    public static void Main() { 

        String str = "abcbbaacb"

        Console.WriteLine(stringReduction(str)); 

    


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

PHP

<?php
// PHP программа для поиска наименьшей возможной длины
// строки только из трех символов

  
// Возвращает наименьшую возможную длину с
// данная операция разрешена.

function stringReduction($str

    $n = strlen($str); 

  

    // Количество вхождений трех разных

    // символы 'a', 'b' и 'c' в строке

    $count = array_fill(0, 3, 0); 

    for ($i = 0; $i < $n; ++$i

        $count[ord($str[$i]) - ord('a')]++; 

  

    // Если все символы одинаковы.

    if ($count[0] == $n || $count[1] == $n || 

        $count[2] == $n

        return $n

  

    // Если присутствуют все символы четного числа

    // раз или все присутствуют нечетное число

    // раз.

    if (($count[0] % 2) == ($count[1] % 2) && 

        ($count[1] % 2) == ($count[2] % 2)) 

        return 2; 

  

    // Ответ равен 1 для всех остальных случаев.

    return 1; 

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

$str = "abcbbaacb"

print(stringReduction($str)); 

      
// Этот код предоставлен mits
?>

Выход:

1

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Адитьей Каматом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Наименьшая длина строки с повторной заменой двух различных смежных

0.00 (0%) 0 votes