Рубрики

Найдите самую длинную подстроку с k уникальными символами в данной строке

Для заданной строки вам необходимо вывести максимально длинную подстроку, содержащую ровно M уникальных символов. Если имеется более одной подстроки максимально длинной длины, выведите любую из них.

Примеры:

"aabbcc", k = 1
Max substring can be any one from {"aa" , "bb" , "cc"}.

"aabbcc", k = 2
Max substring can be any one from {"aabb" , "bbcc"}.

"aabbcc", k = 3
There are substrings with exactly 3 unique characters
{"aabbcc" , "abbcc" , "aabbc" , "abbc" }
Max is "aabbcc" with length 6.

"aaabbb", k = 3
There are only two unique characters, thus show error message. 

Источник: Google Интервью Вопрос.

Метод 1 (грубая сила)
Если длина строки равна n, то может быть n * (n + 1) / 2 возможных подстрок. Простой способ — сгенерировать всю подстроку и проверить каждую, содержит ли она ровно k уникальных символов. Если мы применим эту грубую силу, потребуется O (n 2 ) для генерации всех подстрок и O (n) для проверки каждой из них. Таким образом, в целом это будет идти O (n 3 ).

Мы можем еще больше улучшить это решение, создав хеш-таблицу и, генерируя подстроки, проверять количество уникальных символов, используя эту хеш-таблицу. Таким образом, это улучшится до O (n 2 ).

Метод 2 (линейное время)
Проблема может быть решена в O (n). Идея состоит в том, чтобы поддерживать окно и добавлять элементы в окно до тех пор, пока оно не будет меньше или равно k, при необходимости обновлять наш результат. Если уникальные элементы превышают требуемые в окне, начните удалять элементы с левой стороны.

Ниже приведены реализации выше. Реализации предполагают, что алфавит входной строки содержит только 26 символов (от 'a' до 'z'). Код может быть легко расширен до 256 символов.

C ++

// C ++ программа для поиска самой длинной подстроки с уникальным k
// символы в заданной строке
#include <iostream>
#include <cstring>
#define MAX_CHARS 26

using namespace std;

  
// Эта функция вычисляет количество уникальных символов
// используя ассоциативный массив count []. Возвращает true, если
// нет символов меньше, чем требуется, иначе возвращает
// ложный.

bool isValid(int count[], int k)

{

    int val = 0;

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

        if (count[i] > 0)

            val++;

  

    // Возвращаем true, если k больше или равно val

    return (k >= val);

}

  
// Находит максимальную подстроку с ровно k уникальными символами

void kUniques(string s, int k)

{

    int u = 0; // количество уникальных персонажей

    int n = s.length();

  

    // Ассоциативный массив для хранения количества символов

    int count[MAX_CHARS];

    memset(count, 0, sizeof(count));

  

    // Обход строки, заполняет ассоциативный массив

    // count [] и количество уникальных символов

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

    {

        if (count[s[i]-'a']==0)

            u++;

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

    }

  

    // если не хватает уникальных символов, показать

    // сообщение об ошибке.

    if (u < k)

    {

        cout << "Not enough unique characters";

        return;

    }

  

    // В противном случае возьмем окно с первым элементом в нем.

    // начальные и конечные переменные.

    int curr_start = 0, curr_end = 0;

  

    // Также инициализируем значения для самого длинного окна результата

    int max_window_size = 1, max_window_start = 0;

  

    // Инициализируем ассоциативный массив count [] с нуля

    memset(count, 0, sizeof(count));

  

    count[s[0]-'a']++;  // поставить первый символ

  

    // Начинаем со второго символа и добавляем

    // символы в окне в соответствии с выше

    // объяснение

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

    {

        // Добавить символ 'i [i]' в текущее окно

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

        curr_end++;

  

        // Если в k больше чем уникальных символов

        // текущее окно, удаление с левой стороны

        while (!isValid(count, k))

        {

            count[s[curr_start]-'a']--;

            curr_start++;

        }

  

        // Обновляем максимальный размер окна, если требуется

        if (curr_end-curr_start+1 > max_window_size)

        {

            max_window_size = curr_end-curr_start+1;

            max_window_start = curr_start;

        }

    }

  

    cout << "Max sustring is : "

         << s.substr(max_window_start, max_window_size)

         << " with length " << max_window_size << endl;

}

  
// Функция драйвера

int main()

{

    string s = "aabacbebebe";

    int k = 3;

    kUniques(s, k);

    return 0;

}

Джава

import java.util.Arrays;

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

class GFG {

  

    final static int MAX_CHARS = 26;

  
// Эта функция вычисляет количество уникальных символов
// используя ассоциативный массив count []. Возвращает true, если
// нет символов меньше, чем требуется, иначе возвращает
// ложный.

    static boolean isValid(int count[], int k) {

        int val = 0;

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

            if (count[i] > 0) {

                val++;

            }

        }

  

        // Возвращаем true, если k больше или равно val

        return (k >= val);

    }

  
// Находит максимальную подстроку с ровно k уникальными символами

    static void kUniques(String s, int k) {

        int u = 0; // количество уникальных персонажей

        int n = s.length();

  

        // Ассоциативный массив для хранения количества символов

        int count[] = new int[MAX_CHARS];

        Arrays.fill(count, 0);

        // Обход строки, заполняет ассоциативный массив

        // count [] и количество уникальных символов

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

            if (count[s.charAt(i) - 'a'] == 0) {

                u++;

            }

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

        }

  

        // если не хватает уникальных символов, показать

        // сообщение об ошибке.

        if (u < k) {

            System.out.print("Not enough unique characters");

            return;

        }

  

        // В противном случае возьмем окно с первым элементом в нем.

        // начальные и конечные переменные.

        int curr_start = 0, curr_end = 0;

  

        // Также инициализируем значения для самого длинного окна результата

        int max_window_size = 1, max_window_start = 0;

  

        // Инициализируем ассоциативный массив count [] с нуля

        Arrays.fill(count, 0);

  

        count[s.charAt(0) - 'a']++;  // поставить первый символ

  

        // Начинаем со второго символа и добавляем

        // символы в окне в соответствии с выше

        // объяснение

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

            // Добавить символ 'i [i]' в текущее окно

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

            curr_end++;

  

            // Если в k больше чем уникальных символов

            // текущее окно, удаление с левой стороны

            while (!isValid(count, k)) {

                count[s.charAt(curr_start) - 'a']--;

                curr_start++;

            }

  

            // Обновляем максимальный размер окна, если требуется

            if (curr_end - curr_start + 1 > max_window_size) {

                max_window_size = curr_end - curr_start + 1;

                max_window_start = curr_start;

            }

        }

  

        System.out.println("Max sustring is : "

                + s.substring(max_window_start, max_window_size)

                + " with length " + max_window_size);

    }

  
// Функция драйвера

    static public void main(String[] args) {

        String s = "aabacbebebe";

        int k = 3;

        kUniques(s, k);

    }

}

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

питон

# Программа Python для поиска самой длинной подстроки с уникальным k
# символов в данной строке

MAX_CHARS = 26

  
# Эта функция рассчитывает количество уникальных символов
# используя ассоциативный массив count []. Возвращает true, если
№ № символов меньше, чем требуется, иначе возвращает
# ложный.

def isValid(count, k):

    val = 0

    for i in xrange(MAX_CHARS):

        if count[i] > 0:

            val += 1

  

    # Вернуть true, если k больше или равно val

    return (k >= val)

  
# Находит максимальную подстроку с ровно k уникальных символов

def kUniques(s, k):

    u = 0    # количество уникальных персонажей

    n = len(s)

  

    # Ассоциативный массив для хранения счетчика

    count = [0] * MAX_CHARS

  

    # Трансверс строки, заполняет ассоциативный массив

    # count [] и количество уникальных символов

    for i in xrange(n):

        if count[ord(s[i])-ord('a')] == 0:

            u += 1

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

  

    # Если уникальных персонажей недостаточно, покажите

    # сообщение об ошибке.

    if u < k:

        print "Not enough unique characters"

        return

  

    # В противном случае возьмите окно с первым элементом в нем.

    # начало и конец переменных.

    curr_start = 0

    curr_end = 0

  

    # Инициализировать значения для самого длинного окна результата

    max_window_size = 1

    max_window_start = 0

  

    # Инициализировать ассоциативный массив count [] с нуля

    count = [0] * len(count)

  

    count[ord(s[0])-ord('a')] += 1    # поставить первый символ

  

    # Начните со второго символа и добавьте

    # символов в окне, как указано выше

    # объяснение

    for i in xrange(1,n):

        # Добавить символ 'i [i]' в текущее окно

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

        curr_end+=1

  

        # Если существует более k уникальных символов в

        # текущее окно, удалить с левой стороны

        while not isValid(count, k):

            count[ord(s[curr_start])-ord('a')] -= 1

            curr_start += 1

  

        # Обновите максимальный размер окна, если требуется

        if curr_end-curr_start+1 > max_window_size:

            max_window_size = curr_end-curr_start+1

            max_window_start = curr_start

  

    print "Max substring is : " + s[max_window_start:] \

            + " with length " + str(max_window_size)

  
# Функция драйвера

s = "aabacbebebe"

k = 3

kUniques(s, k)

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

C #

using System;

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

class GFG {

   

    static int MAX_CHARS = 26;

   
// Эта функция вычисляет количество уникальных символов
// используя ассоциативный массив count []. Возвращает true, если
// нет символов меньше, чем требуется, иначе возвращает
// ложный.

    static bool isValid(int[] count, int k) {

        int val = 0;

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

            if (count[i] > 0) {

                val++;

            }

        }

   

        // Возвращаем true, если k больше или равно val

        return (k >= val);

    }

   
// Находит максимальную подстроку с ровно k уникальными символами

    static void kUniques(string s, int k) {

        int u = 0; // количество уникальных персонажей

        int n = s.Length;

   

        // Ассоциативный массив для хранения количества символов

        int[] count = new int[MAX_CHARS];

        Array.Fill(count, 0);

        // Обход строки, заполняет ассоциативный массив

        // count [] и количество уникальных символов

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

            if (count[s[i] - 'a'] == 0) {

                u++;

            }

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

        }

   

        // если не хватает уникальных символов, показать

        // сообщение об ошибке.

        if (u < k) {

            Console.Write("Not enough unique characters");

            return;

        }

   

        // В противном случае возьмем окно с первым элементом в нем.

        // начальные и конечные переменные.

        int curr_start = 0, curr_end = 0;

   

        // Также инициализируем значения для самого длинного окна результата

        int max_window_size = 1, max_window_start = 0;

   

        // Инициализируем ассоциативный массив count [] с нуля

        Array.Fill(count, 0);

   

        count[s[0] - 'a']++;  // поставить первый символ

   

        // Начинаем со второго символа и добавляем

        // символы в окне в соответствии с выше

        // объяснение

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

            // Добавить символ 'i [i]' в текущее окно

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

            curr_end++;

   

            // Если в k больше чем уникальных символов

            // текущее окно, удаление с левой стороны

            while (!isValid(count, k)) {

                count[s[curr_start] - 'a']--;

                curr_start++;

            }

   

            // Обновляем максимальный размер окна, если требуется

            if (curr_end - curr_start + 1 > max_window_size) {

                max_window_size = curr_end - curr_start + 1;

                max_window_start = curr_start;

            }

        }

   

        Console.Write("Max sustring is : "

                + s.Substring(max_window_start, max_window_size)

                + " with length " + max_window_size);

    }

   
// Функция драйвера

    static public void Main() {

        string s = "aabacbebebe";

        int k = 3;

        kUniques(s, k);

    }

}

  


Выход:

Max sustring is : cbebebe with length 7

Сложность по времени: учитывая, что функция isValid () занимает постоянное время, сложность по времени вышеупомянутого решения составляет O (n).

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

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

Найдите самую длинную подстроку с k уникальными символами в данной строке

0.00 (0%) 0 votes