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

// 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 # программа для поиска длины самой длинной подстроки
// без повторяющихся символов

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.