Рубрики

Самая длинная общая подпоследовательность с разрешенными перестановками

Учитывая две строки в нижнем регистре, найдите самую длинную строку, перестановки которой являются подпоследовательностями данных двух строк. Выходная самая длинная строка должна быть отсортирована.

Примеры:

Input  :  str1 = "pink", str2 = "kite"
Output : "ik" 
The string "ik" is the longest sorted string 
whose one permutation "ik" is subsequence of
"pink" and another permutation "ki" is 
subsequence of "kite". 

Input  : str1 = "working", str2 = "women"
Output : "now"

Input  : str1 = "geeks" , str2 = "cake"
Output : "ek"

Input  : str1 = "aaaa" , str2 = "baba"
Output : "aa"

Идея состоит в том, чтобы считать символы в обеих строках.

  1. рассчитайте частоту символов для каждой строки и сохраните их в соответствующих массивах подсчета, скажем, count1 [] для str1 и count2 [] для str2.
  2. Теперь у нас есть массивы для 26 символов. Таким образом, необходимо пройти count1 [] и для любого индекса 'i' добавить символ ('a' + i) в результирующую строку 'result' за минимальное (count1 [i], count2 [i]) время.
  3. Поскольку мы пересекаем массив count в порядке возрастания, наши последние строковые символы будут в отсортированном порядке.
  4. C ++

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

    using namespace std;

      
    // Функция для вычисления самой длинной строки
    // str1 -> первая строка
    // str2 -> вторая строка
    // count1 [] -> массив хешей для вычисления частоты
    // символов в str1
    // count [2] -> массив хешей для вычисления частоты
    // символов в str2
    // результат -> результирующая самая длинная строка, чья
    // перестановки являются подпоследовательностью заданных двух строк

    void longestString(string str1, string str2)

    {

        int count1[26] = {0}, count2[26]= {0};

      

        // вычисляем частоту символов

        for (int i=0; i<str1.length(); i++)

            count1[str1[i]-'a']++;

        for (int i=0; i<str2.length(); i++)

            count2[str2[i]-'a']++;

      

        // Теперь переходим массив хэшей

        string result;

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

      

            // добавляем символ ('a' + i) в результирующий

            // строка 'result' min (count1 [i], count2i])

            // раз

            for (int j=1; j<=min(count1[i],count2[i]); j++)

                result.push_back('a' + i);

      

        cout << result;

    }

      
    // Драйвер программы для запуска дела

    int main()

    {

        string str1 = "geeks", str2 = "cake";

        longestString(str1, str2);

        return 0;

    }

    Джава

    // Java-программа для поиска LCS с разрешенными перестановками

      

    class GFG {

      
    // Функция для вычисления самой длинной строки
    // str1 -> first String
    // str2 -> вторая строка
    // count1 [] -> массив хешей для вычисления частоты
    // символов в str1
    // count [2] -> массив хешей для вычисления частоты
    // символов в str2
    // результат -> результирующая длинная строка, чья
    // перестановки являются подпоследовательностью заданных двух строк

        static void longestString(String str1, String str2) {

            int count1[] = new int[26], count2[] = new int[26];

      

            // вычисляем частоту символов

            for (int i = 0; i < str1.length(); i++) {

                count1[str1.charAt(i) - 'a']++;

            }

            for (int i = 0; i < str2.length(); i++) {

                count2[str2.charAt(i) - 'a']++;

            }

      

            // Теперь переходим массив хэшей

            String result = "";

            for (int i = 0; i < 26; i++) // добавляем символ ('a' + i) в результирующий

            // Строка 'result' min (count1 [i], count2i])

            // раз

            {

                for (int j = 1; j <= Math.min(count1[i], count2[i]); j++) {

                    result += (char)('a' + i);

                }

            }

      

            System.out.println(result);

        }

      
    // Драйвер программы для запуска дела

        public static void main(String[] args) {

            String str1 = "geeks", str2 = "cake";

            longestString(str1, str2);

      

        }

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

    Python 3

    # Python 3 программа для поиска LCS
    # с разрешенными перестановками

      
    # Функция для вычисления самой длинной строки
    # str1 -> первая строка
    # str2 -> вторая строка
    # count1 [] -> хеш-массив для вычисления частоты
    Количество символов в str1
    # count [2] -> массив хешей для вычисления частоты
    Количество символов в str2
    # результат -> результирующая самая длинная строка, чья
    # перестановки являются подпоследовательностью
    количество заданных двух строк

    def longestString(str1, str2):

      

        count1 = [0] * 26

        count2 = [0] * 26

      

        # рассчитать частоту символов

        for i in range( len(str1)):

            count1[ord(str1[i]) - ord('a')] += 1

        for i in range(len(str2)):

            count2[ord(str2[i]) - ord('a')] += 1

      

        # Теперь переходим массив хэшей

        result = ""

        for i in range(26):

      

            # добавить символ ('a' + i) в

            # результирующая строка

            # мин (count1 [i], count2i]) раз

            for j in range(1, min(count1[i],

                                  count2[i]) + 1):

                result = result + chr(ord('a') + i)

      

        print(result)

      
    Код водителя

    if __name__ == "__main__":

          

        str1 = "geeks"

        str2 = "cake"

        longestString(str1, str2)

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

    C #

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

    using System;

      

    class GFG

    {

      
    // Функция для вычисления самой длинной строки
    // str1 -> first String
    // str2 -> вторая строка
    // count1 [] -> массив хешей для вычисления
    // частота символов в str1
    // count [2] -> массив хешей для вычисления
    // частота символов в str2
    // результат -> результирующая длинная строка, чья
    // перестановки являются подпоследовательностью
    // дано две строки

    static void longestString(String str1, 

                              String str2) 

    {

        int []count1 = new int[26];

        int []count2 = new int[26];

      

        // вычисляем частоту символов

        for (int i = 0; i < str1.Length; i++)

        {

            count1[str1[i] - 'a']++;

        }

        for (int i = 0; i < str2.Length; i++) 

        {

            count2[str2[i] - 'a']++;

        }

      

        // Теперь переходим массив хэшей

        String result = "";

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

          

        // добавляем символ ('a' + i) в результирующий

        // Строка 'result' min (count1 [i], count2i])

        // раз

        {

            for (int j = 1; 

                     j <= Math.Min(count1[i], 

                                   count2[i]); j++)

            {

                result += (char)('a' + i);

            }

        }

      
    Console.Write(result);
    }

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

    public static void Main()

    {

        String str1 = "geeks", str2 = "cake";

        longestString(str1, str2);

    }
    }

      
    // Этот код добавлен
    // by PrinciRaj1992

    PHP

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

      
    // Функция для вычисления самой длинной строки
    // str1 -> первая строка
    // str2 -> вторая строка
    // count1 [] -> массив хешей для вычисления частоты
    // символов в str1
    // count [2] -> массив хешей для вычисления частоты
    // символов в str2
    // результат -> результирующая самая длинная строка, чья
    // перестановки являются подпоследовательностью заданных двух строк

    function longestString($str1, $str2)

    {

        $count1 = array_fill(0, 26, NULL);

        $count2 = array_fill(0, 26, NULL);

      

        // вычисляем частоту символов

        for ($i = 0; $i < strlen($str1); $i++)

            $count1[ord($str1[$i]) - ord('a')]++;

        for ($i = 0; $i < strlen($str2); $i++)

            $count2[ord($str2[$i]) - ord('a')]++;

      

        // Теперь переходим массив хэшей

        $result = "";

        for ($i = 0; $i < 26; $i++)

      

            // добавляем символ ('a' + i) в результирующий

            // строка 'result' на min (count1 [$ i],

            // count2 [$ i]) раз

            for ($j = 1; $j <= min($count1[$i], 

                                   $count2[$i]); $j++)

                $result = $result.chr(ord('a') + $i);

      

        echo $result;

    }

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

    $str1 = "geeks";

    $str2 = "cake";

    longestString($str1, $str2);

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


    Выход:

    ek
    

    Сложность времени: O (m + n), где m и n — длины входных строк.
    Вспомогательное пространство: O (1)

    Если у вас есть другой подход к решению этой проблемы, пожалуйста, поделитесь.

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

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

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

    Самая длинная общая подпоследовательность с разрешенными перестановками

    0.00 (0%) 0 votes