Алгоритм поиска самой длинной подстроки-палиндрома
Время на прочтение
5 мин
Количество просмотров 14K
Один из самых прекрасных алгоритмов в информатике, который показывает, как можно получить большое ускорение от “вялого” O(n3) до молниеносного1 O(n), просто посмотрев на проблему с другой точки зрения.
Задача состоит в том, чтобы найти самую длинную подстроку, которая является палиндромом (читается одинаково слева направо и справа налево, например, “racecar”). Так, самый длинный палиндром в строке “Fractions are never odd or even” это “never odd or even” (регистр букв и пробелы игнорируются). Это также имеет практическое применение в биохимии (ГААТТЦ или ЦТТААГ являются палиндромными последовательностями2). К тому же, эту задачу3 часто дают на собеседовании.
Самый простой и прямой подход (при этом самый медленный) – перебирать с начала все подстроки всех длин и проверять, является ли текущая палиндромом:
Псевдокод такого решения
ЦИКЛ по символам всей строки:
ЦИКЛ по всем длинам, начиная с текущего символа:
ЦИКЛ по символам в этой подстроке:явно указывает, что метод со сложностью O(n3) (где n – это длина начальной строки) является быстровозрастающей функцией.
Если бы вместо перебора с самых начал подстрок, мы начинали перебор с середины, это позволило бы нам использовать результаты, которые мы получили на предыдущих шагах.
Например, если мы знаем, что “eve” – это палиндром, то нам потребуется всего одно сравнение, чтобы выяснить, что “level” тоже палиндром. В первом решении нам бы пришлось проверять все полностью с самого начала.
ЦИКЛ по символам строки до середины:
ЦИКЛ по всем длинам, начиная с текущего символа:В таком случае сложность составляет O(n2). Но существуют методы4, позволяющие сделать это еще быстрее.
Один из самых изящных – это алгоритм Манакера5. Он основан на методе, описанном выше, но его временная сложность сокращена до O(n).
Когда палиндромы в строке находятся далеко, оптимизировать нечего. Сложность и так O(n). Проблема появляется, когда они пересекаются, а худшим случаем является строка, состоящая из одной буквы.
Рассмотрим следующую ситуацию. Алгоритм нашел самый короткий зеленый палиндром, самый длинный голубой палиндром и остановился на букве “i”:
Внимательно посмотрев на картинку, можно заметить, что у нас нет необходимости обрабатывать правую часть голубого палиндрома. По определению, это зеркальное отражение левой части, так что полученную левую часть мы можем отразить на правую и получить ее, так сказать, “за бесплатно”.
Однако, это не единственный случай перекрытия. На следующей картинке зеленый палиндром пересекает границу голубого, поэтому его длина должна быть уменьшена.
Опять-таки нет нужды дважды проверять длину отраженного палиндрома: буквы b и x обязаны быть различными, иначе голубой палиндром был бы длиннее.
Наконец, один палиндром может “касаться” другого изнутри. В этом случае нет гарантий, что отраженный палиндром не имеет бОльшую длину, так как мы получаем нижнюю границу его длины:
В идеале мы должны пропускать как нулевые, так и строго ненулевые значения (= все случаи, кроме последнего) в дальнейшей обработке (код 1 ниже). Но в практике (если вообще можно говорить о практике в такой абстрактной задаче) разница между ≥ и = довольно мала (всего одно дополнительное сравнение), поэтому имеет смысл рассматривать все ненулевые значения с помощью ≥ для краткости и читаемости кода (код 2 ниже).
Одна из возможных реализаций алгоритма на питоне:
#код 1
def odd(s):
n = len(s)
h = [0] * n
C = R = 0 # центр и радиус или крайний правый палиндром
besti, bestj = 0, 0 # центр и радиус самого длинного палиндрома
for i in range(n):
if i < C + R: # если есть пересечение
j = h[C-(i-C)] # отражение
if j < C + R - i: # случай A
h[i] = j
continue
elif j > C + R - i: # случай B
h[i] = C + R - i
continue
else: # case C
pass
else: # если нет пересечения
j = 0
while i-j > 0 and i+j<n-1 and s[i-j-1] == s[i+j+1]:
j += 1
h[i] = j
if j > bestj:
besti, bestj = i, j
if i + j > C + R:
C, R = i, j
return s[besti-bestj : besti+bestj+1]Сперва алгоритм пытается найти соответствующее отражение, как описано выше. Затем, если необходимо, последовательно ищет: как в алгоритме со сложностью O(n2), но принимая отраженное значения за начальную точку. В конце если новый палиндром перекрывает больше текста справа, чем предыдущий, то он становится новым крайним правым палиндромом.
Эта функция ищет палиндромы только нечетного размера. Общий подход для работы с палиндромами четного размера таков:
-
вставлять произвольный символ между символами в оригинальной строке, к примеру
‘noon’ -> ‘|n|o|o|n|’, -
находить палиндром нечетного размера,
-
удалять произвольные символы из результата.
Символ “|” необязательно должен отсутствовать в строке. Можно использовать любой символ.
def odd_or_even(s):
return odd('|'+'|'.join(s)+'|').replace('|', '')
>>> odd_or_even('afternoon')
'noon'Немного запутанная версия (труднее для понимания, немного медленнее, но короче) выглядит так:
#код 2
import re
def odd(s):
n = len(s)
h = [0] * n
C = R = 0 # центр и радиус или крайний правый палиндром
besti, bestj = 0, 0 # центр и радиус самого длинного палиндрома
for i in range(n):
j = 0 if i > C+R else min(h[C-(i-C)], C+R-i)
while i-j > 0 and i+j<n-1 and s[i-j-1] == s[i+j+1]:
j += 1
h[i] = j
if j > bestj:
besti, bestj = i, j
if i + j > C + R:
C, R = i, j
return s[besti-bestj : besti+bestj+1]
def manacher(s):
clean = re.sub('W', '', s.lower())
return odd('|'+'|'.join(clean)+'|')[1::2]
>>> manacher('He said: "Madam, I'm Adam!"')
'madamimadam'Как видно, в коде есть два вложенных цикла. Тем не менее, интуитивно понятно, почему сложность O(n). На диаграмме показан массив h.
Внешний цикл соответствует горизонтальному перемещению, внутренний – вертикальному. Каждый шаг – это одно сравнение. Сплошные линии – расчет шагов, пунктирные – пропуск шагов.
Очевидно из диаграммы, что, когда палиндромы не пересекаются, число шагов “вверх” равно количеству горизонтальных “пропускающих” шагов. Для пересекающихся палиндромов чуть более заморочено, но если посчитать число шагов “вверх” и число горизонтальных “пропускающих шагов, то эти числа вновь совпадут. Так что общее число шагов ограничено 2n сравнениями. Не просто n , потому что, в отличие от вертикальных шагов, чтобы понять, пропускать ли горизонтальный шаг или нет, необходимо проделать некую работу (хотя можно изменить реализацию, чтобы пропускать их за постоянное время). Итого временная сложность – O(n).
Алгоритм Манакера позволяет найти самый длинный палиндром в строке (если быть точнее, не просто самый длинный палиндром, а самый длинный палиндром для всех возможных центров) за линейное время, используя очень интуитивный подход, лучше всего описываемый визуально.
Ссылки:
-
Сайт Big-O Cheat Sheet.
-
Статья на Википедии про палиндромные последовательности.
-
Задача на Leetcode про самый длинный палиндром в строке.
-
Статья на Википедии про самый длинный палиндром в строке.
-
Гленн Манакер (1975), “Новый линейный алгоритм для поиска самого длинного палиндрома строки”, журнал ACM.
Given a string str, find the length of the longest substring without repeating characters.
Example:
For “ABDEFGABEF”, the longest substring are “BDEFGA” and “DEFGAB”, with length 6.
For “BBBB” the longest substring is “B”, with length 1.
For “GEEKSFORGEEKS”, there are two longest substrings shown in the below diagrams, with length 7
Method 1 (Simple : O(n3)): We can consider all substrings one by one and check for each substring whether it contains all unique characters or not. There will be n*(n+1)/2 substrings. Whether a substring contains all unique characters or not can be checked in linear time by scanning it from left to right and keeping a map of visited characters.
C++
#include <bits/stdc++.h>
using namespace std;
bool areDistinct(string str, int i, int j)
{
vector<bool> visited(26);
for (int k = i; k <= j; k++) {
if (visited[str[k] - 'a'] == true)
return false;
visited[str[k] - 'a'] = true;
}
return true;
}
int longestUniqueSubsttr(string str)
{
int n = str.size();
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = max(res, j - i + 1);
return res;
}
int main()
{
string str = "geeksforgeeks";
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;
}
C
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
bool areDistinct(char str[], int i, int j)
{
bool visited[26];
for(int i=0;i<26;i++)
visited[i]=0;
for (int k = i; k <= j; k++) {
if (visited[str[k] - 'a'] == true)
return false;
visited[str[k] - 'a'] = true;
}
return true;
}
int longestUniqueSubsttr(char str[])
{
int n = strlen(str);
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = max(res, j - i + 1);
return res;
}
int main()
{
char str[] = "geeksforgeeks";
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
import java.io.*;
import java.util.*;
class GFG{
public static Boolean areDistinct(String str,
int i, int j)
{
boolean[] visited = new boolean[26];
for(int k = i; k <= j; k++)
{
if (visited[str.charAt(k) - 'a'] == true)
return false;
visited[str.charAt(k) - 'a'] = true;
}
return true;
}
public static int longestUniqueSubsttr(String str)
{
int n = str.length();
int res = 0;
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = Math.max(res, j - i + 1);
return res;
}
public static void main(String[] args)
{
String str = "geeksforgeeks";
System.out.println("The input string is " + str);
int len = longestUniqueSubsttr(str);
System.out.println("The length of the longest " +
"non-repeating character " +
"substring is " + len);
}
}
Python3
def areDistinct(str, i, j):
visited = [0] * (26)
for k in range(i, j + 1):
if (visited[ord(str[k]) -
ord('a')] == True):
return False
visited[ord(str[k]) -
ord('a')] = True
return True
def longestUniqueSubsttr(str):
n = len(str)
res = 0
for i in range(n):
for j in range(i, n):
if (areDistinct(str, i, j)):
res = max(res, j - i + 1)
return res
if __name__ == '__main__':
str = "geeksforgeeks"
print("The input is ", str)
len = longestUniqueSubsttr(str)
print("The length of the longest "
"non-repeating character substring is ", len)
C#
using System;
class GFG{
public static bool areDistinct(string str,
int i, int j)
{
bool[] visited = new bool[26];
for(int k = i; k <= j; k++)
{
if (visited[str[k] - 'a'] == true)
return false;
visited[str[k] - 'a'] = true;
}
return true;
}
public static int longestUniqueSubsttr(string str)
{
int n = str.Length;
int res = 0;
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = Math.Max(res, j - i + 1);
return res;
}
public static void Main()
{
string str = "geeksforgeeks";
Console.WriteLine("The input string is " + str);
int len = longestUniqueSubsttr(str);
Console.WriteLine("The length of the longest " +
"non-repeating character " +
"substring is " + len);
}
}
Javascript
<script>
function areDistinct(str, i, j)
{
var visited = new [26];
for(var k = i; k <= j; k++)
{
if (visited[str.charAt(k) - 'a'] == true)
return false;
visited[str.charAt(k) - 'a'] = true;
}
return true;
}
function longestUniqueSubsttr(str)
{
var n = str.length();
var res = 0;
for(var i = 0; i < n; i++)
for(var j = i; j < n; j++)
if (areDistinct(str, i, j))
res = Math.max(res, j - i + 1);
return res;
}
var str = "geeksforgeeks";
document.write("The input string is " + str);
var len = longestUniqueSubsttr(str);
document.write("The length of the longest " +
"non-repeating character " +
"substring is " + len);
</script>
Output
The input string is geeksforgeeks The length of the longest non-repeating character substring is 7
Time Complexity: O(n^3) since we are processing n^2 substrings with maximum length n.
Auxiliary Space: O(1)
Method 2 (Better : O(n2)) The idea is to use window sliding. Whenever we see repetition, we remove the previous occurrence and slide the window.
C++
#include <bits/stdc++.h>
using namespace std;
int longestUniqueSubsttr(string str)
{
int n = str.size();
int res = 0;
for (int i = 0; i < n; i++) {
vector<bool> visited(256);
for (int j = i; j < n; j++) {
if (visited[str[j]] == true)
break;
else {
res = max(res, j - i + 1);
visited[str[j]] = true;
}
}
visited[str[i]] = false;
}
return res;
}
int main()
{
string str = "geeksforgeeks";
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;
}
Java
import java.io.*;
import java.util.*;
class GFG{
public static int longestUniqueSubsttr(String str)
{
int n = str.length();
int res = 0;
for(int i = 0; i < n; i++)
{
boolean[] visited = new boolean[256];
for(int j = i; j < n; j++)
{
if (visited[str.charAt(j)] == true)
break;
else
{
res = Math.max(res, j - i + 1);
visited[str.charAt(j)] = true;
}
}
visited[str.charAt(i)] = false;
}
return res;
}
public static void main(String[] args)
{
String str = "geeksforgeeks";
System.out.println("The input string is " + str);
int len = longestUniqueSubsttr(str);
System.out.println("The length of the longest " +
"non-repeating character " +
"substring is " + len);
}
}
Python3
def longestUniqueSubsttr(str):
n = len(str)
res = 0
for i in range(n):
visited = [0] * 256
for j in range(i, n):
if (visited[ord(str[j])] == True):
break
else:
res = max(res, j - i + 1)
visited[ord(str[j])] = True
visited[ord(str[i])] = False
return res
str = "geeksforgeeks"
print("The input is ", str)
len = longestUniqueSubsttr(str)
print("The length of the longest "
"non-repeating character substring is ", len)
C#
using System;
class GFG{
static int longestUniqueSubsttr(string str)
{
int n = str.Length;
int res = 0;
for(int i = 0; i < n; i++)
{
bool[] visited = new bool[256];
for(int j = i; j < n; j++)
{
if (visited[str[j]] == true)
break;
else
{
res = Math.Max(res, j - i + 1);
visited[str[j]] = true;
}
}
visited[str[i]] = false;
}
return res;
}
static void Main()
{
string str = "geeksforgeeks";
Console.WriteLine("The input string is " + str);
int len = longestUniqueSubsttr(str);
Console.WriteLine("The length of the longest " +
"non-repeating character " +
"substring is " + len );
}
}
Javascript
<script>
function longestUniqueSubsttr(str)
{
var n = str.length;
var res = 0;
for(var i = 0; i < n; i++)
{
var visited = new Array(256);
for(var j = i; j < n; j++)
{
if (visited[str.charCodeAt(j)] == true)
break;
else
{
res = Math.max(res, j - i + 1);
visited[str.charCodeAt(j)] = true;
}
}
}
return res;
}
var str = "geeksforgeeks";
document.write("The input string is " + str);
var len = longestUniqueSubsttr(str);
document.write("The length of the longest " +
"non-repeating character " +
"substring is " + len);
</script>
Output
The input string is geeksforgeeks The length of the longest non-repeating character substring is 7
Time Complexity: O(n^2) since we are traversing each window to remove all repetitions.
Auxiliary Space: O(1)
Method 3 ( Linear Time ): Using this solution the problem can be solved in linear time using the window sliding technique. Whenever we see repetition, we remove the window till the repeated string.
C++
#include <iostream>
#include <string>
using namespace std;
int longestUniqueSubsttr(string str)
{
if (str.length() == 0)
return 0;
if (str.length() == 1)
return 1;
int maxLength = 0;
bool visited[256] = { false };
int left = 0, right = 0;
for (; right < str.length(); right++) {
if (visited[str[right]] == false)
visited[str[right]] = true;
else {
maxLength = max(maxLength, (right - left));
while (left < right) {
if (str[left] != str[right])
visited[str[left]] = false;
else {
left++;
break;
}
left++;
}
}
}
maxLength = max(maxLength, (right - left));
return maxLength;
}
int main()
{
string s = "GeeksForGeeks!";
cout << longestUniqueSubsttr(s) << endl;
return 0;
}
Java
import java.io.*;
class GFG {
public static int longestUniqueSubsttr(String str)
{
String test = "";
int maxLength = -1;
if (str.isEmpty()) {
return 0;
}
else if (str.length() == 1) {
return 1;
}
for (char c : str.toCharArray()) {
String current = String.valueOf(c);
if (test.contains(current)) {
test = test.substring(test.indexOf(current)
+ 1);
}
test = test + String.valueOf(c);
maxLength = Math.max(test.length(), maxLength);
}
return maxLength;
}
public static void main(String[] args)
{
String str = "geeksforgeeks";
System.out.println("The input string is " + str);
int len = longestUniqueSubsttr(str);
System.out.println("The length of the longest "
+ "non-repeating character "
+ "substring is " + len);
}
}
Python3
import math
def longestUniqueSubsttr(str):
test = ""
maxLength = -1
if (len(str) == 0):
return 0
elif(len(str) == 1):
return 1
for c in list(str):
current = "".join(c)
if (current in test):
test = test[test.index(current) + 1:]
test = test + "".join(c)
maxLength = max(len(test), maxLength)
return maxLength
string = "geeksforgeeks"
print("The input string is", string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character substring is", length)
C#
using System;
public class GFG
{
public static int longestUniqueSubsttr(String str)
{
var test = "";
var maxLength = -1;
if (str.Length == 0)
{
return 0;
}
else if (str.Length == 1)
{
return 1;
}
foreach (char c in str.ToCharArray())
{
var current = c+"";
if (test.Contains(current))
{
test = test.Substring(test.IndexOf(current) + 1);
}
test = test + c;
maxLength = Math.Max(test.Length,maxLength);
}
return maxLength;
}
public static void Main(String[] args)
{
var str = "geeksforgeeks";
Console.WriteLine("The input string is " + str);
var len = GFG.longestUniqueSubsttr(str);
Console.WriteLine("The length of the longest " + "non-repeating character " + "substring is " + len.ToString());
}
}
Javascript
function longestUniqueSubsttr( str)
{
if (str.length == 0)
return 0;
if (str.length == 1)
return 1;
let maxLength = 0;
let visited=[];
for(let i=0;i<256;i++)
visited.push(false);
let left = 0, right = 0;
for (; right < str.length; right++) {
if (visited[str.charCodeAt(right)] == false)
visited[str.charCodeAt(right)] = true;
else {
maxLength = Math.max(maxLength, (right - left));
while (left < right) {
if (str.charCodeAt(left) != str.charCodeAt(right))
visited[str.charCodeAt(left)] = false;
else {
left++;
break;
}
left++;
}
}
}
maxLength = Math.max(maxLength, (right - left));
return maxLength;
}
let s = "GeeksForGeeks!";
console.log(longestUniqueSubsttr(s));
Time Complexity: O(n) since we slide the window whenever we see any repetitions.
Auxiliary Space: O(1)
Method 4 (Linear Time): Let us talk about the linear time solution now. This solution uses extra space to store the last indexes of already visited characters. The idea is to scan the string from left to right, keep track of the maximum length Non-Repeating Character Substring seen so far in res. When we traverse the string, to know the length of current window we need two indexes.
1) Ending index ( j ) : We consider current index as ending index.
2) Starting index ( i ) : It is same as previous window if current character was not present in the previous window. To check if the current character was present in the previous window or not, we store last index of every character in an array lasIndex[]. If lastIndex[str[j]] + 1 is more than previous start, then we updated the start index i. Else we keep same i.
Below is the implementation of the above approach :
C++
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
int longestUniqueSubsttr(string str)
{
int n = str.size();
int res = 0;
vector<int> lastIndex(NO_OF_CHARS, -1);
int i = 0;
for (int j = 0; j < n; j++) {
i = max(i, lastIndex[str[j]] + 1);
res = max(res, j - i + 1);
lastIndex[str[j]] = j;
}
return res;
}
int main()
{
string str = "geeksforgeeks";
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;
}
Java
import java.util.*;
public class GFG {
static final int NO_OF_CHARS = 256;
static int longestUniqueSubsttr(String str)
{
int n = str.length();
int res = 0;
int [] lastIndex = new int[NO_OF_CHARS];
Arrays.fill(lastIndex, -1);
int i = 0;
for (int j = 0; j < n; j++) {
i = Math.max(i, lastIndex[str.charAt(j)] + 1);
res = Math.max(res, j - i + 1);
lastIndex[str.charAt(j)] = j;
}
return res;
}
public static void main(String[] args)
{
String str = "geeksforgeeks";
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);
}
}
Python3
def longestUniqueSubsttr(string):
last_idx = {}
max_len = 0
start_idx = 0
for i in range(0, len(string)):
if string[i] in last_idx:
start_idx = max(start_idx, last_idx[string[i]] + 1)
max_len = max(max_len, i-start_idx + 1)
last_idx[string[i]] = i
return max_len
string = "geeksforgeeks"
print("The input string is " + string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character" +
" substring is " + str(length))
C#
using System;
public class GFG
{
static int NO_OF_CHARS = 256;
static int longestUniqueSubsttr(string str)
{
int n = str.Length;
int res = 0;
int [] lastIndex = new int[NO_OF_CHARS];
Array.Fill(lastIndex, -1);
int i = 0;
for (int j = 0; j < n; j++)
{
i = Math.Max(i, lastIndex[str[j]] + 1);
res = Math.Max(res, j - i + 1);
lastIndex[str[j]] = j;
}
return res;
}
static public void Main ()
{
string str = "geeksforgeeks";
Console.WriteLine("The input string is " + str);
int len = longestUniqueSubsttr(str);
Console.WriteLine("The length of "+
"the longest non repeating character is " +
len);
}
}
Javascript
<script>
var NO_OF_CHARS = 256;
function longestUniqueSubsttr(str)
{
var n = str.length();
var res = 0;
var lastIndex = new [NO_OF_CHARS];
Arrays.fill(lastIndex, -1);
var i = 0;
for (var j = 0; j < n; j++) {
i = Math.max(i, lastIndex[str.charAt(j)] + 1);
res = Math.max(res, j - i + 1);
lastIndex[str.charAt(j)] = j;
}
return res;
}
var str = "geeksforgeeks";
document.write("The input string is " + str);
var len = longestUniqueSubsttr(str);
document.write("The length of the longest non repeating character is " + len);
</script>
Output
The input string is geeksforgeeks The length of the longest non-repeating character substring is 7
Time Complexity: O(n + d) where n is length of the input string and d is number of characters in input string alphabet. For example, if string consists of lowercase English characters then value of d is 26.
Auxiliary Space: O(d)
Alternate Implementation :
C++
#include <bits/stdc++.h>
using namespace std;
int longestUniqueSubsttr(string s)
{
map<char, int> seen ;
int maximum_length = 0;
int start = 0;
for(int end = 0; end < s.length(); end++)
{
if (seen.find(s[end]) != seen.end())
{
start = max(start, seen[s[end]] + 1);
}
seen[s[end]] = end;
maximum_length = max(maximum_length,
end - start + 1);
}
return maximum_length;
}
int main()
{
string s = "geeksforgeeks";
cout << "The input String is " << s << endl;
int length = longestUniqueSubsttr(s);
cout<<"The length of the longest non-repeating character "
<<"substring is "
<< length;
}
Java
import java.util.*;
class GFG {
static int longestUniqueSubsttr(String s)
{
HashMap<Character, Integer> seen = new HashMap<>();
int maximum_length = 0;
int start = 0;
for(int end = 0; end < s.length(); end++)
{
if(seen.containsKey(s.charAt(end)))
{
start = Math.max(start, seen.get(s.charAt(end)) + 1);
}
seen.put(s.charAt(end), end);
maximum_length = Math.max(maximum_length, end-start + 1);
}
return maximum_length;
}
public static void main(String []args)
{
String s = "geeksforgeeks";
System.out.println("The input String is " + s);
int length = longestUniqueSubsttr(s);
System.out.println("The length of the longest non-repeating character substring is " + length);
}
}
Python3
def longestUniqueSubsttr(string):
seen = {}
maximum_length = 0
start = 0
for end in range(len(string)):
if string[end] in seen:
start = max(start, seen[string[end]] + 1)
seen[string[end]] = end
maximum_length = max(maximum_length, end-start + 1)
return maximum_length
string = "geeksforgeeks"
print("The input string is", string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character substring is", length)
C#
using System;
using System.Collections.Generic;
class GFG {
static int longestUniqueSubsttr(string s)
{
Dictionary<char, int> seen = new Dictionary<char, int>();
int maximum_length = 0;
int start = 0;
for(int end = 0; end < s.Length; end++)
{
if(seen.ContainsKey(s[end]))
{
start = Math.Max(start, seen[s[end]] + 1);
}
seen[s[end]] = end;
maximum_length = Math.Max(maximum_length, end-start + 1);
}
return maximum_length;
}
static void Main() {
string s = "geeksforgeeks";
Console.WriteLine("The input string is " + s);
int length = longestUniqueSubsttr(s);
Console.WriteLine("The length of the longest non-repeating character substring is " + length);
}
}
Javascript
<script>
function longestUniqueSubsttr(s)
{
let seen = new Map();
let maximum_length = 0;
let start = 0;
for(let end = 0; end < s.length; end++)
{
if (seen.has(s[end]))
{
start = Math.max(start, seen.get(s[end]) + 1);
}
seen.set(s[end],end)
maximum_length = Math.max(maximum_length, end - start + 1);
}
return maximum_length;
}
let s = "geeksforgeeks"
document.write(`The input String is ${s}`)
let length = longestUniqueSubsttr(s);
document.write(`The length of the longest non-repeating character substring is ${length}`)
</script>
Output
The input String is geeksforgeeks The length of the longest non-repeating character substring is 7
Time Complexity: O(n + d) where n is length of the input string and d is number of characters in input string alphabet. For example, if string consists of lowercase English characters then value of d is 26.
Auxiliary Space: O(d)
As an exercise, try the modified version of the above problem where you need to print the maximum length NRCS also (the above program only prints the length of it).
Method 5 (Linear time): In this method we will apply KMP Algorithm technique, to solve the problem. We maintain an Unordered Set to keep track of the maximum non repeating char sub string (Instead of standard LPS array of KMP). When ever we find a repeating char, then we clear the Set and reset len to zero. Rest everything is almost similar to KMP.
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubstrDistinctChars(string s)
{
if (s.length() == 0)
return 0;
int n = s.length();
set<char> st;
int len = 1;
st.insert(s[0]);
int i = 1;
int maxLen = 0;
while (i < n)
{
if (s[i] != s[i - 1] && st.find(s[i]) == st.end())
{
st.insert(s[i]);
len++;
i++;
if (len > maxLen)
{
maxLen = len;
}
}
else
{
if (len == 1)
{
i++;
}
else
{
st.clear();
i = i - len + 1;
len = 0;
}
}
}
return max(maxLen, len);
}
int main()
{
string str = "abcabcbb";
cout << "The input string is " << str << endl;
int len = longestSubstrDistinctChars(str);
cout << "The length of the longest non-repeating character substring " << len;
return 0;
}
Java
import java.util.*;
class GFG {
public static int longestSubstrDistinctChars(String s)
{
if (s.length() == 0) {
return 0;
}
int n = s.length();
HashSet<Character> st = new HashSet<Character>();
int len = 1;
st.add(s.charAt(0));
int i = 1;
int maxLen = 0;
while (i < n) {
if (s.charAt(i) != s.charAt(i - 1)
&& !st.contains(s.charAt(i))) {
st.add(s.charAt(i));
len++;
i++;
if (len > maxLen) {
maxLen = len;
}
}
else {
if (len == 1) {
i++;
}
else {
st.clear();
i = i - len + 1;
len = 0;
}
}
}
return Math.max(maxLen, len);
}
public static void main(String[] args)
{
String str = "abcabcbb";
System.out.println("The input string is " + str);
int len = longestSubstrDistinctChars(str);
System.out.println(
"The length of the longest non-repeating character substring "
+ len);
}
}
Python3
def longestSubstrDistinctChars(s):
if len(s) == 0:
return 0
n = len(s)
st = set()
leng = 1
st.add(s[0])
i = 1
maxLen = 0
while i < n:
if s[i] != s[i - 1] and s[i] not in st:
st.add(s[i])
leng += 1
i += 1
if leng > maxLen:
maxLen = leng
else:
if leng == 1:
i += 1
else:
st.clear()
i = i - leng + 1
leng = 0
return max(maxLen, leng)
if __name__ == '__main__':
string = "abcabcbb"
print("The input string is " + string)
leng = longestSubstrDistinctChars(string)
print("The length of the longest non-repeating character substring " + str(leng))
C#
using System;
using System.Linq;
using System.Collections.Generic;
class GFG {
static int longestSubstrDistinctChars(string s)
{
if (s.Length == 0)
return 0;
int n = s.Length;
HashSet<char> st=new HashSet<char>();
int len = 1;
st.Add(s[0]);
int i = 1;
int maxLen = 0;
while (i < n)
{
if (s[i] != s[i - 1] && !st.Contains(s[i]))
{
st.Add(s[i]);
len++;
i++;
if (len > maxLen)
{
maxLen = len;
}
}
else
{
if (len == 1)
{
i++;
}
else
{
st.Clear();
i = i - len + 1;
len = 0;
}
}
}
return Math.Max(maxLen, len);
}
public static void Main (string[] args)
{
string str = "abcabcbb";
Console.WriteLine("The input string is " + str);
int len = longestSubstrDistinctChars(str);
Console.WriteLine("The length of the longest non-repeating character substring " + len);
}
}
Javascript
<script>
function longestSubstrDistinctChars(s) {
if(s.length === 0)
return 0;
const n = s.length;
const st = new Set();
let len = 1;
st.add(s[0]);
let i =1;
let maxLen = 0;
while(i<n){
if(s[i]!==s[i-1] && !st.has(s[i])){
st.add(s[i]);
len++;
i++;
if(len>maxLen){
maxLen = len;
}
} else {
if(len ===1) {i++;}
else{
st.clear();
i=i-len+1;
len = 0;
}
}
}
return maxLen || len;
}
var str = "abcabcbb";
document.write("The input string is " + str);
var len = longestSubstrDistinctChars(str);
document.write("The length of the longest non-repeating character substring " + len);
</script>
Output
The input string is abcabcbb The length of the longest non-repeating character substring 3
Time Complexity : O(n) where n is the input string length
Auxiliary Space: O(m) where m is the length of the resultant sub string
Last Updated :
25 Jan, 2023
Like Article
Save Article
Продолжаем разбирать задачи с сайта LeetCode. На этот раз — посложнее:
Есть строка s — нужно найти длину самой длинной подстроки, в которой каждый символ используется только один раз.
Например:
если s = “abcabcbb”, то ответ будет 3, потому что строка без повторений — это “abc”;
если s = “bbbbb”, то ответ будет 1, потому что самая длинная подстрока тут будет из одного символа;
если s = “pwwkew”, то ответ будет 3, потому что тут две самые одинаково длинные подстроки — “wke” и “kew”, в которых по 3 символа.
Такие алгоритмы иногда используются для выявления закономерностей и поиска общих элементов, поэтому их тоже могут спросить на собеседованиях.
Решение: использовать встроенные функции для работы со строками
Самое простое решение — собирать отдельную подстроку из символов и смотреть каждый раз, есть очередной символ в этой подстроке или нет. Если нет — добавляем его в конец и смотрим дальше. А если очередной символ там уже есть, то в подстроке оставляем только то, что идёт после этого символа, и добавляем туда текущий.
Например, если у нас в подстроке хранится “abcdf” и мы снова встречаем b, то делаем так:
- Получаем номер символа b в подстроке → он равен 1 (если интересно, почему не 2, — почитайте, почему счёт в программировании начинается с нуля, а не с единицы).
- Формируем новую строку, начиная с 1 символа и до конца → “cdf”.
- Добавляем к ней в конец наш текущий символ b → “cdfb”.
Так шаг за шагом мы проверим все вложенные строки и найдём самую длинную без повторов. Звучит сложно, но в коде всё выглядит гораздо проще. Почитайте комментарии, чтобы разобраться в каждом шаге:
# исходная строка
s = 'abcabcdcc'
# здесь будет наш ответ
res = 0
# на старте у нас пустая подстрока
sub = ''
# перебираем все символы в исходной строке
for char in s:
# если символа нет в подстроке
if char not in sub:
# добавляем его туда
sub += char
# смотрим, максимальный ли это результат, и если да — запоминаем его
res = max(res, len(sub))
# если символ в подстроке есть
else:
# получаем индекс текущего символа в подстроке
cut = sub.index(char)
# сокращаем нашу подстроку: оставляем только то, что идёт после символа-дубликата, и добавляем к строке текущий символ
sub = sub[cut+1:] + char
# выводим результат на экран
print(res)Решение: проверить всю вложенную строку
Зайдём с другой стороны — напишем функцию, которая будет проверять, есть в указанной подстроке повторяющиеся символы или нет. Логика будет такая:
- Передаём в функцию начальный и конечный индекс, который определяет границы подстроки.
- Заводим массив, в который будем складывать проверенные символы и проверять на дубли.
- По очереди проверяем все символы в указанном диапазоне и смотрим, есть ли очередной символ в нашем массиве.
- Если есть — выводим False, что означает, что в подстроке есть повторяющиеся символы.
- Если символа нет — добавляем его в наш массив.
- Если мы проверили все символы и ни одного не было в том массиве — возвращаем True, то есть повторов нет.
Теперь запишем это на Python:
# исходная строка
s = 'abcabcdcc'
# функция, которая проверит, есть ли в подстроке повторяющиеся символы
# на вход отправляем начальную и конечную позицию в строке для проверки
def check(start, end):
# создаём пустое множество
chars = set()
# делаем цикл от начального до конечного символа
for i in range(start, end + 1):
# получаем очередной символ из строки
c = s[i]
# если символа уже есть в множестве
if c in chars:
# возвращаем False — в строке есть повторяющиеся символы
return False
# добавляем символ в множество
chars.add(c)
# если дошли досюда — возвращаем True
return TrueТеперь перейдём к основной части. Раз мы научились проверять, есть повторы в подстроке или нет, то нам остаётся только найти и проверить все вложенные строки. Сделаем это обычным перебором с вложенным циклом: будем проверять все подстроки, сначала начиная с первого символа, потом со второго и так далее. При этом мы будем каждый раз считать и запоминать максимальную длину подстроки без повторов, которая у нас получилась:
# --- основной алгоритм ---
# получаем длину строки
n = len(s)
# здесь будет наш ответ
res = 0
# перебираем символы от первого до последнего
for i in range(n):
# перебираем символы от текущего до последнего
for j in range(i, n):
# если в получившейся подстроке нет повторяющихся символов
if check(i, j):
# смотрим, максимальный ли это результат, и если да — запоминаем его
res = max(res, j - i + 1)
# выводим результат на экран
print(res)Объединим обе части и получим готовый код:
# исходная строка
s = 'abcabcdcc'
# функция, которая проверит, есть ли в подстроке повторяющиеся символы
# на вход отправляем начальную и конечную позицию в строке для проверки
def check(start, end):
# создаём пустое множество
chars = set()
# делаем цикл от начального до конечного символа
for i in range(start, end + 1):
# получаем очередной символ из строки
c = s[i]
# если символа уже есть в множестве
if c in chars:
# возвращаем False — в строке есть повторяющиеся символы
return False
# добавляем символ в множество
chars.add(c)
# если дошли досюда — возвращаем True
return True
# --- основной алгоритм ---
# получаем длину строки
n = len(s)
# здесь будет наш ответ
res = 0
# перебираем символы от первого до последнего
for i in range(n):
# перебираем символы от текущего до последнего
for j in range(i, n):
# если в получившейся подстроке нет повторяющихся символов
if check(i, j):
# смотрим, максимальный ли это результат, и если да — запоминаем его
res = max(res, j - i + 1)
# выводим результат на экран
print(res)Вёрстка:
Кирилл Климентьев
Учитывая строку, найдите самую длинную подстроку, содержащую различные символы.
Задача отличается от задачи поиска самой длинной подпоследовательности с различными символами. В отличие от подпоследовательностей, подстроки должны занимать последовательные позиции в исходной строке.
Например,
Input: findlongestsubstring
Output: The longest substring with all distinct characters is dlongest or ubstring
Input: longestsubstr
Output: The longest substring with all distinct characters is longest
Input: abbcdafeegh
Output: The longest substring with all distinct characters is bcdafe
Input: aaaaaa
Output: The longest substring with all distinct characters is a
Потренируйтесь в этой проблеме
Простым решением было бы сгенерировать все заданные подстроки строки и вернуть самую длинную подстроку, содержащую все отдельные символы. Временная сложность этого решения O(n3) так как это занимает O(n2) время для генерации всех подстрок для строки длины n а также O(n) время обработки каждой подстроки.
Мы можем легко решить эту проблему в O(n) время. Идея состоит в том, чтобы использовать раздвижное окно техника. В методе скользящего окна поддерживается окно, удовлетворяющее ограничениям задачи. Окно нестабильно, если оно нарушает ограничения задачи, и оно пытается стабилизироваться, увеличивая или уменьшая свой размер.
Таким образом, для текущей задачи окно (подстрока) является стабильным, если оно содержит все различные символы в любой точке. Если окно содержит повторяющиеся символы, оно сжимается путем удаления символов слева до тех пор, пока снова не станет стабильным. Стабильное окно имеет тенденцию увеличивать свой размер, добавляя к нему символы, пока оно снова не станет нестабильным. Процесс продолжается до тех пор, пока окно не достигнет последнего символа в строке. В каждой точке размер окна меняется, обновите максимальный размер окна.
Ниже приведена реализация этой идеи на C++, Java и Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <string> #include <vector> using namespace std; // Определяем диапазон символов #define CHAR_RANGE 128 // Функция для поиска самой длинной подстроки, содержащей все различные // символы в нем с помощью скользящего окна string findLongestSubstring(string str, int n) { // логический массив для обозначения символов, присутствующих в текущем окне vector<bool> window(CHAR_RANGE); // сохраняет самые длинные границы подстроки int begin = 0, end = 0; // `[low…high]` сохраняет границы скользящего окна for (int low = 0, high = 0; high < n; high++) { // если текущий символ присутствует в текущем окне if (window[str[high]]) { // удаляем символы слева от окна до // встречаем текущий символ while (str[low] != str[high]) { window[str[low++]] = false; } low++; // удалить текущий символ } else { // если текущий символ отсутствует в текущем // окно, включаем его window[str[high]] = true; // обновляем максимальный размер окна при необходимости if (end – begin < high – low) { begin = low; end = high; } } } // вернуть самую длинную подстроку, найденную в `str[begin…end]` return str.substr(begin, end – begin + 1); } int main() { string str = “abbcdafeegh”; int n = str.length(); cout << findLongestSubstring(str, n); return 0; } |
Скачать Выполнить код
результат:
bcdafe
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
class Main { // Определяем диапазон символов private static final int CHAR_RANGE = 128; // Функция для поиска самой длинной подстроки со всеми // отдельные символы с использованием скользящего окна public static String findLongestSubstring(String str) { // базовый вариант if (str == null || str.length() == 0) { return str; } // логический массив для обозначения символов, присутствующих в текущем окне boolean[] window = new boolean[CHAR_RANGE]; // сохраняет самые длинные границы подстроки int begin = 0, end = 0; // `[low…high]` сохраняет границы скользящего окна for (int low = 0, high = 0; high < str.length(); high++) { // если текущий символ присутствует в текущем окне if (window[str.charAt(high)]) { // удаляем символы слева от окна до // встречаем текущий символ while (str.charAt(low) != str.charAt(high)) { window[str.charAt(low)] = false; low++; } low++; // удалить текущий символ } else { // если текущий символ отсутствует в текущем // окно, включаем его window[str.charAt(high)] = true; // обновляем максимальный размер окна при необходимости if (end – begin < high – low) { begin = low; end = high; } } } // вернуть самую длинную подстроку, найденную в `str[begin…end]` return str.substring(begin, end + 1); } public static void main(String[] args) { String str = “abbcdafeegh”; System.out.print(findLongestSubstring(str)); } } |
Скачать Выполнить код
результат:
bcdafe
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Функция поиска самой длинной подстроки со всеми # отдельные символы с использованием скользящего окна def findLongestSubstring(s): # Список # для отметки символов, присутствующих в текущем окне window = {} # хранит самые длинные границы подстроки begin = end = 0 # `[low…high]` сохраняет границы скользящего окна low = high = 0 while high < len(s): #, если текущий символ присутствует в текущем окне if window.get(s[high]): # удалить символы слева от окна до # сталкиваемся с текущим персонажем while s[low] != s[high]: window[s[low]] = False low = low + 1 low = low + 1 # удалить текущий персонаж else: #, если текущий символ отсутствует в текущем # Окно #, включите его window[s[high]] = True # обновляет максимальный размер окна при необходимости if end – begin < high – low: begin = low end = high high = high + 1 # возвращает самую длинную подстроку, найденную в `s[begin…end]` return s[begin:end + 1] if __name__ == ‘__main__’: s = ‘abbcdafeegh’ print(findLongestSubstring(s)) |
Скачать Выполнить код
результат:
bcdafe
Временная сложность приведенного выше решения равна O(n) поскольку он выполняет два обхода заданной строки длины n.
Найти самую длинную подстроку без повторяющихся символов
1. обзор
В этом руководстве сравниваются способы поиска самой длинной подстроки уникальных букв с использованием Java. Например, самая длинная подстрока уникальных букв в «CODINGISAWESOME» – это «NGISAWE».
2. Метод грубой силы
Начнем с наивного подхода. Начнем сwe can examine each substring whether it contains unique characters:
String getUniqueCharacterSubstringBruteForce(String input) {
String output = "";
for (int start = 0; start < input.length(); start++) {
Set visited = new HashSet<>();
int end = start;
for (; end < input.length(); end++) {
char currChar = input.charAt(end);
if (visited.contains(currChar)) {
break;
} else {
visited.add(currChar);
}
}
if (output.length() < end - start + 1) {
output = input.substring(start, end);
}
}
return output;
}Поскольку возможных подстрокn*(n+1)/2,the time complexity of this approach is O(n^2).
3. Оптимизированный подход
Теперь давайте посмотрим на оптимизированный подход. Мы начинаем обход строки слева направо и отслеживаем:
-
текущая подстрока с неповторяющимися символами с помощью индексаstart иend
-
самая длинная неповторяющаяся подстрокаoutput
-
таблица поиска уже символовvisited
String getUniqueCharacterSubstring(String input) {
Map visited = new HashMap<>();
String output = "";
for (int start = 0, end = 0; end < input.length(); end++) {
char currChar = input.charAt(end);
if (visited.containsKey(currChar)) {
start = Math.max(visited.get(currChar)+1, start);
}
if (output.length() < end - start + 1) {
output = input.substring(start, end + 1);
}
visited.put(currChar, end);
}
return output;
}Для каждого нового персонажа мы ищем его в уже посещенных персонажах. Если символ уже был посещен и является частью текущей подстроки с неповторяющимися символами, мы обновляем стартовый индекс. В противном случае мы продолжим обход строки.
Поскольку мы обходим строку только один раз,the time complexity will be linear, or O(n).
4. тестирование
Наконец, давайте тщательно протестируем нашу реализацию, чтобы убедиться, что она работает:
@Test
void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected() {
assertEquals("", getUniqueCharacterSubstring(""));
assertEquals("A", getUniqueCharacterSubstring("A"));
assertEquals("ABCDEF", getUniqueCharacterSubstring("AABCDEF"));
assertEquals("ABCDEF", getUniqueCharacterSubstring("ABCDEFF"));
assertEquals("NGISAWE", getUniqueCharacterSubstring("CODINGISAWESOME"));
assertEquals("be coding", getUniqueCharacterSubstring("always be coding"));
}Здесь мы пробуем иtest boundary conditions as well as the more typical use cases.
5. Заключение
В этом руководстве мы узнали, как использовать технику скользящего окна, чтобы найти самую длинную подстроку с неповторяющимися символами.
