Рубрики

Длина самой длинной подстроки без повторяющихся символов

По заданной строке str найдите длину самой длинной подстроки без повторяющихся символов.

  • Для «ABDEFGABEF» самой длинной подстрокой являются «BDEFGA» и «DEFGAB» длиной 6.
  • Для «BBBB» самая длинная подстрока — «B» длиной 1.
  • Для «GEEKSFORGEEKS» есть две самые длинные подстроки, показанные на диаграммах ниже, длиной 7
  • ,

Требуемая временная сложность составляет O (n), где n — длина строки.

Метод 1 (простой) : Мы можем рассмотреть все подстроки одну за другой и проверить для каждой подстроки, содержит ли она все уникальные символы или нет. Там будет n * (n + 1) / 2 подстроки. Независимо от того, содержит ли подстрока все уникальные символы или нет, ее можно проверить за линейное время, отсканировав ее слева направо и сохранив карту посещенных символов. Временная сложность этого решения будет O (n ^ 3).

Метод 2 (линейное время) : давайте поговорим о решении линейного времени сейчас. Это решение использует дополнительное пространство для хранения последних индексов уже посещенных символов. Идея состоит в том, чтобы сканировать строку слева направо, отслеживая максимальную длину неповторяющейся символьной подстроки ( NRCS ), наблюдаемой до сих пор. Пусть максимальная длина будет max_len. Когда мы пересекаем строку, мы также отслеживаем длину текущей NRCS, используя переменную cur_len. Для каждого нового символа мы ищем его в уже обработанной части строки (для этой цели используется временный массив с именем visit []). Если его нет, то мы увеличиваем cur_len на 1. Если есть, то есть два случая:

  1. Предыдущий экземпляр символа не является частью текущей NRCS (NRCS, которая находится в процессе). В этом случае нам нужно просто увеличить cur_len на 1.
  2. Если предыдущий экземпляр является частью текущей NRCS, то наша текущая NRCS изменится. Он становится подстрокой, начиная со следующего символа предыдущего экземпляра и заканчивая текущим сканированным символом. Нам также нужно сравнить cur_len и max_len, прежде чем менять текущую NRCS (или менять cur_len).

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

C ++

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

using namespace std;

#define NO_OF_CHARS 256

  

int longestUniqueSubsttr(string str)

{

    int n = str.size();

    int cur_len = 1; // длина текущей подстроки

    int max_len = 1; // результат

    int prev_index; // предыдущий индекс

      

    int* visited = new int[sizeof(int) * NO_OF_CHARS];

  

    / * Инициализировать посещенный массив как -1, -1 используется для

    указать, что персонаж еще не посещался * /

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

        visited[i] = -1;

  

    / * Пометить первый символ как посещенный, сохранив индекс

    первого символа в посещаемом массиве. * /

    visited[str[0]] = 0;

  

    / * Начать со второго символа. Первый персонаж

    уже обработано (cur_len и max_len инициализированы

    как 1, и посещенный [str [0]] устанавливается * /

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

        prev_index = visited[str[i]];

  

        / * Если текущий символ отсутствует в

        уже обработанная подстрока или она не является частью

        текущая NRCS, тогда сделай cur_len ++ * /

        if (prev_index == -1 || i - cur_len > prev_index)

            cur_len++;

  

        / * Если текущий символ присутствует в настоящее время

        считается NRCS, затем обновите NRCS, чтобы начать с

        следующий символ предыдущего экземпляра. * /

        else {

            / * Кроме того, когда мы меняем NRCS, мы

            следует также проверить, является ли длина

            предыдущий NRCS был больше, чем max_len или

            не.*/

            if (cur_len > max_len)

                max_len = cur_len;

  

            cur_len = i - prev_index;

        }

  

        // обновляем индекс текущего символа

        visited[str[i]] = i;

    }

  

    // Сравнить длину последней NRCS с max_len и

    // обновляем max_len при необходимости

    if (cur_len > max_len)

        max_len = cur_len;

  

    free(visited); // свободная память, выделенная для посещенных

    return max_len;

}

  

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

int main()

{

    string str = "ABDEFGABEF";

      

    cout << "The input string is " << str << endl;

      

    int len = longestUniqueSubsttr(str);

      

    cout << "The length of the longest non-repeating "

            "character substring is "

        << len;

    return 0;

}

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

С

// Программа на C, чтобы найти длину самой длинной подстроки
// без повторяющихся символов
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NO_OF_CHARS 256

  

int min(int a, int b);

  

int longestUniqueSubsttr(char* str)

{

    int n = strlen(str);

    int cur_len = 1; // длина текущей подстроки

    int max_len = 1; // результат

    int prev_index; // предыдущий индекс

    int i;

    int* visited = (int*)malloc(sizeof(int) * NO_OF_CHARS);

  

    / * Инициализировать посещенный массив как -1, -1 используется для

       указать, что персонаж еще не посещался * /

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

        visited[i] = -1;

  

    / * Пометить первый символ как посещенный, сохранив индекс

       первого символа в посещаемом массиве. * /

    visited[str[0]] = 0;

  

    / * Начать со второго символа. Первый персонаж

       уже обработано (cur_len и max_len инициализированы

       как 1, и посещенный [str [0]] устанавливается * /

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

        prev_index = visited[str[i]];

  

        / * Если текущий символ отсутствует в

           уже обработанная подстрока или она не является частью

           текущая NRCS, тогда сделай cur_len ++ * /

        if (prev_index == -1 || i - cur_len > prev_index)

            cur_len++;

  

        / * Если текущий символ присутствует в настоящее время

           считается NRCS, затем обновите NRCS, чтобы начать с

           следующий символ предыдущего экземпляра. * /

        else {

            / * Кроме того, когда мы меняем NRCS, мы

               следует также проверить, является ли длина

               предыдущий NRCS был больше, чем max_len или

               не.*/

            if (cur_len > max_len)

                max_len = cur_len;

  

            cur_len = i - prev_index;

        }

  

        // обновляем индекс текущего символа

        visited[str[i]] = i;

    }

  

    // Сравнить длину последней NRCS с max_len и

    // обновляем max_len при необходимости

    if (cur_len > max_len)

        max_len = cur_len;

  

    free(visited); // свободная память, выделенная для посещенных

    return max_len;

}

  
/ * Полезная функция для получения минимум двух целых чисел * /

int min(int a, int b)

{

    return (a > b) ? b : a;

}

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

int main()

{

    char str[] = "ABDEFGABEF";

    printf("The input string is %s n", str);

    int len = longestUniqueSubsttr(str);

    printf("The length of the longest non-repeating "

           "character substring is %d",

           len);

    return 0;

}

Джава

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

public class GFG {

  

    static final int NO_OF_CHARS = 256;

  

    static int longestUniqueSubsttr(String str)

    {

        int n = str.length();

        int cur_len = 1; // длина текущей подстроки

        int max_len = 1; // результат

        int prev_index; // предыдущий индекс

        int i;

        int visited[] = new int[NO_OF_CHARS];

  

        / * Инициализировать посещенный массив как -1, -1

         используется, чтобы указать, что символ не был

         посетил еще. * /

        for (i = 0; i < NO_OF_CHARS; i++) {

            visited[i] = -1;

        }

  

        / * Пометить первый символ как посещенный, сохранив

             индекс первого символа в посещаемом массиве. * /

        visited[str.charAt(0)] = 0;

  

        / * Начать со второго символа. Первый персонаж

           уже обработано (cur_len и max_len инициализированы

         как 1, и посещенный [str [0]] устанавливается * /

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

            prev_index = visited[str.charAt(i)];

  

            / * Если текущий символ отсутствует в

           уже обработанная подстрока или нет

              часть текущей NRCS, затем сделайте cur_len ++ * /

            if (prev_index == -1 || i - cur_len > prev_index)

                cur_len++;

  

            / * Если текущий символ присутствует в настоящее время

               считается NRCS, затем обновите NRCS, чтобы начать с

               следующий символ предыдущего экземпляра. * /

            else {

                / * Кроме того, когда мы меняем NRCS, мы

                   следует также проверить, является ли длина

                   предыдущий NRCS был больше, чем max_len или

                   не.*/

                if (cur_len > max_len)

                    max_len = cur_len;

  

                cur_len = i - prev_index;

            }

  

            // обновляем индекс текущего символа

            visited[str.charAt(i)] = i;

        }

  

        // Сравнить длину последней NRCS с max_len и

        // обновляем max_len при необходимости

        if (cur_len > max_len)

            max_len = cur_len;

  

        return max_len;

    }

  

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

    public static void main(String[] args)

    {

        String str = "ABDEFGABEF";

        System.out.println("The input string is " + str);

        int len = longestUniqueSubsttr(str);

        System.out.println("The length of "

                           + "the longest non repeating character is " + len);

    }

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

питон

# Программа Python, чтобы найти длину самой длинной подстроки
# без повторяющихся символов

NO_OF_CHARS = 256

  

def longestUniqueSubsttr(string):

    n = len(string)

    cur_len = 1        # Хранить длину текущей подстроки

    max_len = 1        # Чтобы сохранить результат

    prev_index = 0    # Сохранить предыдущий индекс

    i = 0

  

    # Инициализировать посещенный массив как -1, -1 используется для указания

    # этот персонаж еще не посещался.

    visited = [-1] * NO_OF_CHARS

  

    # Пометить первый символ как посещенный, сохранив индекс

    # первый символ в посещаемом массиве.

    visited[ord(string[0])] = 0

  

    # Начните со второго символа. Первый персонаж уже

    # обработано (cur_len и max_len инициализируются как 1, и

    # посещено [str [0]] установлено

    for i in xrange(1, n):

        prev_index = visited[ord(string[i])]

  

        # Если текущий символ не присутствует в уже

        # обработана подстрока или она не является частью текущей NRCS,

        # тогда сделай cur_len ++

        if prev_index == -1 or (i - cur_len > prev_index):

            cur_len+= 1

  

        # Если текущий символ присутствует в настоящее время считается

        # NRCS, затем обновите NRCS, чтобы начать со следующего символа

        # предыдущий экземпляр.

        else:

            # Кроме того, когда мы меняем NRCS, мы должны также

            # проверить, была ли длина предыдущей NRCS больше

            # чем max_len или нет.

            if cur_len > max_len:

                max_len = cur_len

  

            cur_len = i - prev_index

  

        # обновить индекс текущего символа

        visited[ord(string[i])] = i

  

    # Сравните длину последней NRCS с max_len и обновите

    # max_len при необходимости

    if cur_len > max_len:

        max_len = cur_len

  

    return max_len

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

string = "ABDEFGABEF"

print "The input string is " + string

length = longestUniqueSubsttr(string)

print ("The length of the longest non-repeating character" +

       " substring is " + str(length))

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

C #

// C # программа для поиска длины самой длинной подстроки
// без повторяющихся символов

using System;

  

class GFG {

    static int NO_OF_CHARS = 256;

  

    static int longestUniqueSubsttr(String str)

    {

        int n = str.Length;

  

        // длина текущей подстроки

        int cur_len = 1;

  

        // результат

        int max_len = 1;

  

        // предыдущий индекс

        int prev_index;

  

        int i;

        int[] visited = new int[NO_OF_CHARS];

  

        / * Инициализировать посещенный массив как -1, -1

        используется, чтобы указать, что символ не был

        посетил еще. * /

        for (i = 0; i < NO_OF_CHARS; i++) {

            visited[i] = -1;

        }

  

        / * Пометить первый символ как посещенный, сохранив

            индекс первого символа в посещаемом массиве. * /

        visited[str[0]] = 0;

  

        / * Начать со второго символа. Первый персонаж

        уже обработано (cur_len и max_len инициализированы

        как 1, и посещенный [str [0]] устанавливается * /

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

            prev_index = visited[str[i]];

  

            / * Если текущий символ отсутствует в

        уже обработанная подстрока или нет

            часть текущей NRCS, затем сделайте cur_len ++ * /

            if (prev_index == -1 || i - cur_len > prev_index)

                cur_len++;

  

            / * Если текущий символ присутствует в настоящее время

            считается NRCS, затем обновите NRCS, чтобы начать с

            следующий символ предыдущего экземпляра. * /

            else {

                / * Кроме того, когда мы меняем NRCS, мы

                следует также проверить, является ли длина

                предыдущий NRCS был больше, чем max_len или

                не.*/

                if (cur_len > max_len)

                    max_len = cur_len;

  

                cur_len = i - prev_index;

            }

  

            // обновляем индекс текущего символа

            visited[str[i]] = i;

        }

  

        // Сравнить длину последней NRCS с max_len и

        // обновляем max_len при необходимости

        if (cur_len > max_len)

            max_len = cur_len;

  

        return max_len;

    }

  

    // Драйвер программы

    public static void Main()

    {

        String str = "ABDEFGABEF";

        Console.WriteLine("The input string is " + str);

        int len = longestUniqueSubsttr(str);

        Console.Write("The length of "

                      + "the longest non repeating character is " + len);

    }

}

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


Выход

  The input string is ABDEFGABEF
  The length of the longest non-repeating character substring is 6

Сложность времени: O (n + d), где n — длина входной строки, а d — количество символов в алфавите входной строки. Например, если строка состоит из строчных букв английского алфавита, то значение d равно 26.
Вспомогательное пространство: O (d)

В качестве упражнения попробуйте модифицированную версию вышеуказанной задачи, где вам также необходимо напечатать NRCS максимальной длины (вышеуказанная программа печатает только ее длину).

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

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

Длина самой длинной подстроки без повторяющихся символов

0.00 (0%) 0 votes