Найти самую длинную подстроку без повторяющихся символов
Учитывая string S of length N найти самую длинную подстроку без повторяющихся символов.
Пример:
Вход: "stackoverflow"
Выход: "stackoverfl"
Если есть два таких кандидата, вернитесь сначала слева. Мне нужен алгоритм линейного времени и постоянного пространства.
Ответы
Ответ 1
-
Вам понадобится начальный и конечный локатор (/указатель) для строки и массив, в котором вы храните информацию для каждого символа: произошло ли это хотя бы один раз?
-
Начните с начала строки, оба локатора указывают на начало строки.
-
Перемещайте указатель конца вправо, пока не найдете повтор (или не достигните конца строки). Для каждого обработанного символа сохраните его в массиве. Когда остановлено, сохраните позицию, если это самая большая подстрока. Также помните повторный характер.
-
Теперь сделайте то же самое с локатором запуска, при обработке каждого символа удалите его флаги из массива. Перемещайте локатор, пока не найдете более раннее вхождение повторяющегося символа.
-
Вернитесь к шагу 3, если вы еще не достигли конца строки.
Всего: O (N)
Ответ 2
import java.util.HashSet;
public class SubString {
public static String subString(String input){
HashSet<Character> set = new HashSet<Character>();
String longestOverAll = "";
String longestTillNow = "";
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (set.contains(c)) {
longestTillNow = "";
set.clear();
}
longestTillNow += c;
set.add(c);
if (longestTillNow.length() > longestOverAll.length()) {
longestOverAll = longestTillNow;
}
}
return longestOverAll;
}
public static void main(String[] args) {
String input = "substringfindout";
System.out.println(subString(input));
}
}
Ответ 3
Вы сохраняете массив, указывающий позицию, в которой произошел последний символ. Для удобства все символы имели место в позиции -1. Вы повторяете строку, содержащую окно, если символ повторяется в этом окне, вы прерываете префикс, который заканчивается первым вхождением этого символа. Всюду вы сохраняете самую длинную длину. Здесь реализована реализация python:
def longest_unique_substr(S):
# This should be replaced by an array (size = alphabet size).
last_occurrence = {}
longest_len_so_far = 0
longest_pos_so_far = 0
curr_starting_pos = 0
curr_length = 0
for k, c in enumerate(S):
l = last_occurrence.get(c, -1)
# If no repetition within window, no problems.
if l < curr_starting_pos:
curr_length += 1
else:
# Check if it is the longest so far
if curr_length > longest_len_so_far:
longest_pos_so_far = curr_starting_pos
longest_len_so_far = curr_length
# Cut the prefix that has repetition
curr_length -= l - curr_starting_pos
curr_starting_pos = l + 1
# In any case, update last_occurrence
last_occurrence[c] = k
# Maybe the longest substring is a suffix
if curr_length > longest_len_so_far:
longest_pos_so_far = curr_starting_pos
longest_len_so_far = curr_length
return S[longest_pos_so_far:longest_pos_so_far + longest_len_so_far]
Ответ 4
Редакция:
следующая - реализация concesus. Это произошло со мной после моей первоначальной публикации. чтобы не удалять оригинал, он представлен ниже:
public static String longestUniqueString(String S) {
int start = 0, end = 0, length = 0;
boolean bits[] = new boolean[256];
int x = 0, y = 0;
for (; x < S.length() && y < S.length() && length < S.length() - x; x++) {
bits[S.charAt(x)] = true;
for (y++; y < S.length() && !bits[S.charAt(y)]; y++) {
bits[S.charAt(y)] = true;
}
if (length < y - x) {
start = x;
end = y;
length = y - x;
}
while(y<S.length() && x<y && S.charAt(x) != S.charAt(y))
bits[S.charAt(x++)]=false;
}
return S.substring(start, end);
}//
ОРИГИНАЛЬНАЯ ПОЧТА:
Вот мои два цента. Включены тестовые строки. boolean bits [] = new boolean [256] может быть больше, чтобы охватить некоторые более крупные кодировки.
public static String longestUniqueString(String S) {
int start=0, end=0, length=0;
boolean bits[] = new boolean[256];
int x=0, y=0;
for(;x<S.length() && y<S.length() && length < S.length()-x;x++) {
Arrays.fill(bits, false);
bits[S.charAt(x)]=true;
for(y=x+1;y<S.length() && !bits[S.charAt(y)];y++) {
bits[S.charAt(y)]=true;
}
if(length<y-x) {
start=x;
end=y;
length=y-x;
}
}
return S.substring(start,end);
}//
public static void main(String... args) {
String input[][] = { { "" }, { "a" }, { "ab" }, { "aab" }, { "abb" },
{ "aabc" }, { "abbc" }, { "aabbccdefgbc" },
{ "abcdeafghicabcdefghijklmnop" },
{ "abcdeafghicabcdefghijklmnopqrabcdx" },
{ "zxxaabcdeafghicabcdefghijklmnopqrabcdx" },
{"aaabcdefgaaa"}};
for (String[] a : input) {
System.out.format("%s *** GIVES *** {%s}%n", Arrays.toString(a),
longestUniqueString(a[0]));
}
}
Ответ 5
Вот еще одно решение с двумя строковыми переменными:
public static String getLongestNonRepeatingString(String inputStr){
if(inputStr == null){
return null;
}
String maxStr = "";
String tempStr = "";
for(int i=0; i < inputStr.length(); i++){
// 1. if tempStr contains new character, then change tempStr
if(tempStr.contains("" + inputStr.charAt(i))){
tempStr = tempStr.substring(tempStr.lastIndexOf(inputStr.charAt(i)) + 1);
}
// 2. add new character
tempStr = tempStr + inputStr.charAt(i);
// 3. replace maxStr with tempStr if tempStr is longer
if(maxStr.length() < tempStr.length()){
maxStr = tempStr;
}
}
return maxStr;
}
Ответ 6
Алгоритм в JavaScript (с большим количеством комментариев)..
/**
Given a string S find longest substring without repeating characters.
Example:
Input: "stackoverflow"
Output: "stackoverfl"
Input: "stackoverflowabcdefghijklmn"
Output: "owabcdefghijklmn"
*/
function findLongestNonRepeatingSubStr(input) {
var chars = input.split('');
var currChar;
var str = "";
var longestStr = "";
var hash = {};
for (var i = 0; i < chars.length; i++) {
currChar = chars[i];
if (!hash[chars[i]]) { // if hash doesn't have the char,
str += currChar; //add it to str
hash[chars[i]] = {index:i};//store the index of the char
} else {// if a duplicate char found..
//store the current longest non-repeating chars. until now
//In case of equal-length, <= right-most str, < will result in left most str
if(longestStr.length <= str.length) {
longestStr = str;
}
//Get the previous duplicate char index
var prevDupeIndex = hash[currChar].index;
//Find all the chars AFTER previous duplicate char and current one
var strFromPrevDupe = input.substring(prevDupeIndex + 1, i);
//*NEW* longest string will be chars AFTER prevDupe till current char
str = strFromPrevDupe + currChar;
//console.log(str);
//Also, Reset hash to letters AFTER duplicate letter till current char
hash = {};
for (var j = prevDupeIndex + 1; j <= i; j++) {
hash[input.charAt(j)] = {index:j};
}
}
}
return longestStr.length > str.length ? longestStr : str;
}
//console.log("stackoverflow => " + findLongestNonRepeatingSubStr("stackoverflow"));
//returns stackoverfl
//console.log("stackoverflowabcdefghijklmn => " +
findLongestNonRepeatingSubStr("stackoverflowabcdefghijklmn")); //returns owabcdefghijklmn
//console.log("1230123450101 => " + findLongestNonRepeatingSubStr("1230123450101")); //
returns 234501
Ответ 7
Мы можем рассматривать все подстроки один за другим и проверять каждую подстроку, содержит ли она все уникальные символы или нет. Будут n * (n + 1)/2 подстроки. Может ли подстановка содержать все уникальные символы или нет, можно проверить в линейном времени на сканирование слева направо и сохранение карты посещаемых символов. Временной сложностью этого решения было бы O (n ^ 3).
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class LengthOfLongestSubstringWithOutRepeatingChar {
public static void main(String[] args)
{
String s="stackoverflow";
//allSubString(s);
System.out.println("result of find"+find(s));
}
public static String find(String s)
{
List<String> allSubsring=allSubString(s);
Set<String> main =new LinkedHashSet<String>();
for(String temp:allSubsring)
{
boolean a = false;
for(int i=0;i<temp.length();i++)
{
for(int k=temp.length()-1;k>i;k--)
{
if(temp.charAt(k)==temp.charAt(i))
a=true;
}
}
if(!a)
{
main.add(temp);
}
}
/*for(String x:main)
{
System.out.println(x);
}*/
String res=null;
int min=0,max=s.length();
for(String temp:main)
{
if(temp.length()>min&&temp.length()<max)
{
min=temp.length();
res=temp;
}
}
System.out.println(min+"ha ha ha"+res+"he he he");
return res;
}
//substrings left to right ban rahi hai
private static List<String> allSubString(String str) {
List<String> all=new ArrayList<String>();
int c=0;
for (int i = 0; i < str.length(); i++) {
for (int j = 0; j <= i; j++) {
if (!all.contains(str.substring(j, i + 1)))
{
c++;
all.add(str.substring(j, i + 1));
}
}
}
for(String temp:all)
{
System.out.println("substring :-"+temp);
}
System.out.println("count"+c);
return all;
}
}
Ответ 8
Другое решение O (n) JavaScript. Он не изменяет строки во время цикла; он просто отслеживает смещение и длину самой длинной подстроки до сих пор:
function longest(str) {
var hash = {}, start, end, bestStart, best;
start = end = bestStart = best = 0;
while (end < str.length) {
while (hash[str[end]]) hash[str[start++]] = 0;
hash[str[end]] = 1;
if (++end - start > best) bestStart = start, best = end - start;
}
return str.substr(bestStart, best);
}
// I/O for snippet
document.querySelector('input').addEventListener('input', function () {
document.querySelector('span').textContent = longest(this.value);
});
Enter word:<input><br>
Longest: <span></span>
Ответ 9
![введите описание изображения здесь]()
простой фрагмент питона
l = длина p = позиция
maxl = maxlength maxp = maxposition
Ответ 10
I was asked the same question in an interview.
Я написал код Python 3, чтобы найти первое вхождение подстроки со всеми различными символами. В моих реализациях я начинаю с index = 0 и перебираю входную строку. Во время итерации использовали Python dict seems для хранения индексов символов во входной строке, которые были посещены в итерации.
В итерации, если char c, не находит в текущей подстроке & ndash; вызвать исключение KeyError
если c обнаружил дублирующийся символ в текущей подстроке (как c ранее появлялся во время итерации - назвал этот индекс last_seen), запустите новую подстроку
def lds(string: str) -> str:
""" returns first longest distinct substring in input 'string' """
seens = {}
start, end, curt_start = 0, 0, 0
for curt_end, c in enumerate(string):
try:
last_seen = seens[c]
if last_seen < curt_start:
raise KeyError(f"{c!r} not found in {string[curt_start: curt_end]!r}")
if end - start < curt_end - curt_start:
start, end = curt_start, curt_end
curt_start = last_seen + 1
except KeyError:
pass
seens[c] = curt_end
else:
# case when the longest substring is suffix of the string, here curt_end
# do not point to a repeating char hance included in the substring
if string and end - start < curt_end - curt_start + 1:
start, end = curt_start, curt_end + 1
return string[start: end]
Ответ 11
Самая длинная подстрока без повторяющихся символов в питоне
public int lengthOfLongestSubstring(String s) {
if(s.equals(""))
return 0;
String[] arr = s.split("");
HashMap<String,Integer> map = new HashMap<>();
Queue<String> q = new LinkedList<>();
int l_till = 1;
int l_all = 1;
map.put(arr[0],0);
q.add(arr[0]);
for(int i = 1; i < s.length(); i++){
if (map.containsKey(arr[i])) {
if(l_till > l_all){
l_all = l_till;
}
while(!q.isEmpty() && !q.peek().equals(arr[i])){
map.remove(q.remove());
}
if(!q.isEmpty())
map.remove(q.remove());
q.add(arr[i]);
map.put(arr[i],i);
//System.out.println(q);
//System.out.println(map);
l_till = q.size();
}
else {
l_till = l_till + 1;
map.put(arr[i],i);
q.add(arr[i]);
}
}
if(l_till > l_all){
l_all = l_till;
}
return l_all;
}
Ответ 12
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;
public class LongestSubString2 {
public static void main(String[] args) {
String input = "stackoverflowabcdefghijklmn";
List<String> allOutPuts = new ArrayList<String>();
TreeMap<Integer, Set> map = new TreeMap<Integer, Set>();
for (int k = 0; k < input.length(); k++) {
String input1 = input.substring(k);
String longestSubString = getLongestSubString(input1);
allOutPuts.add(longestSubString);
}
for (String str : allOutPuts) {
int strLen = str.length();
if (map.containsKey(strLen)) {
Set set2 = (HashSet) map.get(strLen);
set2.add(str);
map.put(strLen, set2);
} else {
Set set1 = new HashSet();
set1.add(str);
map.put(strLen, set1);
}
}
System.out.println(map.lastKey());
System.out.println(map.get(map.lastKey()));
}
private static void printArray(Object[] currentObjArr) {
for (Object obj : currentObjArr) {
char str = (char) obj;
System.out.println(str);
}
}
private static String getLongestSubString(String input) {
Set<Character> set = new LinkedHashSet<Character>();
String longestString = "";
int len = input.length();
for (int i = 0; i < len; i++) {
char currentChar = input.charAt(i);
boolean isCharAdded = set.add(currentChar);
if (isCharAdded) {
if (i == len - 1) {
String currentStr = getStringFromSet(set);
if (currentStr.length() > longestString.length()) {
longestString = currentStr;
}
}
continue;
} else {
String currentStr = getStringFromSet(set);
if (currentStr.length() > longestString.length()) {
longestString = currentStr;
}
set = new LinkedHashSet<Character>(input.charAt(i));
}
}
return longestString;
}
private static String getStringFromSet(Set<Character> set) {
Object[] charArr = set.toArray();
StringBuffer strBuff = new StringBuffer();
for (Object obj : charArr) {
strBuff.append(obj);
}
return strBuff.toString();
}
}
Ответ 13
Это мое решение, и оно было принято с помощью leetcode. Тем не менее, после того, как я увидел статистику, я увидел, что решения с множеством решений имеют гораздо более быстрый результат... что означает, что мое решение составляет около 600 мс для всех их тестовых случаев, и большинство решений js составляют около 200-300 мкс. может сказать мне, почему мое решение работает медленно?
var lengthOfLongestSubstring = function(s) {
var arr = s.split("");
if (s.length === 0 || s.length === 1) {
return s.length;
}
var head = 0,
tail = 1;
var str = arr[head];
var maxL = 0;
while (tail < arr.length) {
if (str.indexOf(arr[tail]) == -1) {
str += arr[tail];
maxL = Math.max(maxL, str.length);
tail++;
} else {
maxL = Math.max(maxL, str.length);
head = head + str.indexOf(arr[tail]) + 1;
str = arr[head];
tail = head + 1;
}
}
return maxL;
};
Ответ 14
Я отправляю O (n ^ 2) в python. Я просто хочу знать, имеет ли метод, упомянутый Кароли Хорватом, какие-либо шаги, похожие на существующие алгоритмы поиска/сортировки?
Мой код:
def main():
test='stackoverflow'
tempstr=''
maxlen,index=0,0
indexsubstring=''
print 'Original string is =%s\n\n' %test
while(index!=len(test)):
for char in test[index:]:
if char not in tempstr:
tempstr+=char
if len(tempstr)> len(indexsubstring):
indexsubstring=tempstr
elif (len(tempstr)>=maxlen):
maxlen=len(tempstr)
indexsubstring=tempstr
break
tempstr=''
print 'max substring length till iteration with starting index =%s is %s'%(test[index],indexsubstring)
index+=1
if __name__=='__main__':
main()
Ответ 15
Просто и легко
import java.util.Scanner;
public class longestsub {
static Scanner sn = new Scanner(System.in);
static String word = sn.nextLine();
public static void main(String[] args) {
System.out.println("The Length is " +check(word));
}
private static int check(String word) {
String store="";
for (int i = 0; i < word.length(); i++) {
if (store.indexOf(word.charAt(i))<0) {
store = store+word.charAt(i);
}
}
System.out.println("Result word " +store);
return store.length();
}
}
Ответ 16
Не совсем оптимизированный, но простой ответ в Python
def lengthOfLongestSubstring(s):
temp,maxlen,newstart = {},0,0
for i,x in enumerate(s):
if x in temp:
newstart = max(newstart,s[:i].rfind(x)+1)
else:
temp[x] = 1
maxlen = max(maxlen, len(s[newstart:i + 1]))
return maxlen
Я думаю, что дорогостоящее дело rfind, поэтому оно не совсем оптимизировано.
Ответ 17
Проверено и работает. Для легкого понимания, я полагаю, там есть ящик для писем.
Функция:
public int lengthOfLongestSubstring(String s) {
int maxlen = 0;
int start = 0;
int end = 0;
HashSet<Character> drawer = new HashSet<Character>();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
if (drawer.contains(ch)) {
//search for ch between start and end
while (s.charAt(start)!=ch) {
//drop letter from drawer
drawer.remove(s.charAt(start));
start++;
}
//Do not remove from drawer actual char (it the new recently found)
start++;
end++;
}
else {
drawer.add(ch);
end++;
int _maxlen = end-start;
if (_maxlen>maxlen) {
maxlen=_maxlen;
}
}
}
return maxlen;
}
Ответ 18
Это мое решение. Надеюсь, что это поможет.
function longestSubstringWithoutDuplication(str) {
var max = 0;
//if empty string
if (str.length === 0){
return 0;
} else if (str.length === 1){ //case if the string length is 1
return 1;
}
//loop over all the chars in the strings
var currentChar,
map = {},
counter = 0; //count the number of char in each substring without duplications
for (var i=0; i< str.length ; i++){
currentChar = str.charAt(i);
//if the current char is not in the map
if (map[currentChar] == undefined){
//push the currentChar to the map
map[currentChar] = i;
if (Object.keys(map).length > max){
max = Object.keys(map).length;
}
} else { //there is duplacation
//update the max
if (Object.keys(map).length > max){
max = Object.keys(map).length;
}
counter = 0; //initilize the counter to count next substring
i = map[currentChar]; //start from the duplicated char
map = {}; // clean the map
}
}
return max;
}
Ответ 19
вот мои javascript и cpp-реализации с большими деталями: https://algorithm.pingzhang.io/String/longest_substring_without_repeating_characters.html
Мы хотим найти самую длинную подстроку без повторяющихся символов. Первое, что приходит мне в голову, это то, что нам нужна хеш-таблица для хранения каждого символа в подстроке, чтобы при входе нового персонажа мы можем легко узнать, находится ли этот символ уже в подстроке или нет. Я называю это valueIdxHash. Тогда подстрока имеет startIdx и endIdx. Поэтому нам нужна переменная, чтобы отслеживать начальный индекс подстроки, и я называю ее startIdx. Предположим, что мы находимся в индексе i, и у нас уже есть подстрока (startIdx, i - 1). Теперь мы хотим проверить, может ли эта подстрока продолжать расти или нет.
Если valueIdxHash содержит str[i], это означает, что это повторяющийся символ. Но нам все равно нужно проверить, находится ли этот повторяющийся символ в подстроке (startIdx, i - 1). Поэтому нам нужно получить индекс str[i], который появился в последний раз, а затем сравнить этот индекс с startIdx.
- Если
startIdx больше, это означает, что последний появился str[i] вне подстроки. Таким образом, подстрока может продолжать расти.
- Если
startIdx меньше, это означает, что последнее появилось str[i] внутри подстроки. Таким образом, подстрока больше не может расти. startIdx будет обновляться как valueIdxHash[str[i]] + 1, и новая подстрока (valueIdxHash[str[i]] + 1, i) может продолжать расти.
Если valueIdxHash не содержит str[i], подстрока может продолжать расти.
Ответ 20
import java.util.HashMap;
import java.util.HashSet;
public class SubString {
public static String subString(String input) {
String longesTillNOw = "";
String longestOverAll = "";
HashMap<Character,Integer> chars = new HashMap<>();
char[] array=input.toCharArray();
int start=0;
for (int i = 0; i < array.length; i++) {
char charactor = array[i];
if (chars.containsKey(charactor) ) {
start=chars.get(charactor)+1;
i=start;
chars.clear();
longesTillNOw = "";
} else {
chars.put(charactor,i);
longesTillNOw = longesTillNOw + charactor;
if (longesTillNOw.length() > longestOverAll.length()) {
longestOverAll = longesTillNOw;
}
}
}
return longestOverAll;
}
public static void main(String[] args) {
String input = "stackoverflowabcdefghijklmn";
System.out.println(subString(input));
}
}
Ответ 21
Я изменил свое решение, чтобы "найти длину самой длинной подстроки без повторяющихся символов".
public string LengthOfLongestSubstring(string s) {
var res = 0;
var dict = new Dictionary<char, int>();
var start = 0;
for(int i =0; i< s.Length; i++)
{
if(dict.ContainsKey(s[i]))
{
start = Math.Max(start, dict[s[i]] + 1); //update start index
dict[s[i]] = i;
}
else
{
dict.Add(s[i], i);
}
res = Math.Max(res, i - start + 1); //track max length
}
return s.Substring(start,res);
}
Ответ 22
Вот два способа подхода к этой проблеме в JavaScript.
A Метод Brute Force состоит в том, чтобы дважды прокручивать строку, проверяя каждую подстроку на каждую другую подстроку и находим максимальную длину, где подстрока уникальна. Нам понадобятся две функции: одна, чтобы проверить, является ли подстрока уникальной, и вторая функция для выполнения нашего двойного цикла.
// O(n) time
const allUnique = str => {
const set = [...new Set(str)];
return (set.length == str.length) ? true: false;
}
// O(n^3) time, O(k) size where k is the size of the set
const lengthOfLongestSubstring = str => {
let result = 0,
maxResult = 0;
for (let i=0; i<str.length-1; i++) {
for (let j=i+1; j<str.length; j++) {
if (allUnique(str.substring(i, j))) {
result = str.substring(i, j).length;
if (result > maxResult) {
maxResult = result;
}
}
}
return maxResult;
}
}
У этого есть временная сложность O(n^3), поскольку мы выполняем двойной цикл O(n^2), а затем еще один цикл поверх этого O(n) для нашей уникальной функции. Пространство - это размер нашего набора, который может быть обобщен на O(n) или более точно O(k), где k - размер набора.
A Жадный подход - это цикл только один раз и отслеживать максимальную уникальную длину подстроки по мере продвижения. Мы можем использовать либо массив, либо хэш-карту, но я думаю, что новый метод . Include() - это классно, поэтому позвольте использовать это.
const lengthOfLongestSubstring = str => {
let result = [],
maxResult = 0;
for (let i=0; i<str.length; i++) {
if (!result.includes(str[i])) {
result.push(str[i]);
} else {
maxResult = i;
}
}
return maxResult;
}
Это имеет временную сложность O(n) и пространственную сложность O(1).
Ответ 23
Вопрос: Найти самую длинную подстроку без повторяющихся символов. Пример 1:
import java.util.LinkedHashMap;
import java.util.Map;
public class example1 {
public static void main(String[] args) {
String a = "abcabcbb";
// output => 3
System.out.println( lengthOfLongestSubstring(a));
}
private static int lengthOfLongestSubstring(String a) {
if(a == null || a.length() == 0) {return 0 ;}
int res = 0 ;
Map<Character , Integer> map = new LinkedHashMap<>();
for (int i = 0; i < a.length(); i++) {
char ch = a.charAt(i);
if (!map.containsKey(ch)) {
//If ch is not present in map, adding ch into map along with its position
map.put(ch, i);
}else {
/*
If char ch is present in Map, reposition the cursor i to the position of ch and clear the Map.
*/
i = map.put(ch, i);// updation of index
map.clear();
}//else
res = Math.max(res, map.size());
}
return res;
}
}
если вам нужна самая длинная строка без повторяющихся символов в качестве выходных данных, сделайте это внутри цикла for:
String res ="";// global
int len = 0 ;//global
if(len < map.size()) {
len = map.size();
res = map.keySet().toString();
}
System.out.println("len -> " + len);
System.out.println("res => " + res);
Ответ 24
Эта проблема может быть решена за O (n) временной сложности. Инициализируйте три переменные
- Начало (индекс указывает на начало неповторяющейся подстроки, Инициализируйте его как 0).
- Конец (индекс, указывающий на конец неповторяющейся подстроки, Инициализируйте его как 0)
- Hasmap (Объект, содержащий последние посещенные позиции индекса символов. Пример: {'a': 0, 'b': 1} для строки "ab")
Шаги: переберите строку и выполните следующие действия.
- Если текущий символ отсутствует в hashmap(), добавьте его как hashmap, символ в качестве ключа и его индекс в качестве значения.
-
Если текущий символ присутствует в hashmap, то
a) Проверьте, является ли начальный индекс меньше или равен значению, присутствующему в хэш-карте для символа (последний индекс того же символа, который был ранее посещен),
б) меньше назначенного значения начальных переменных в качестве значения хеш-карт + 1 (последний посещенный ранее индекс того же символа + 1);
c) Обновите хэш-карту, переопределив текущее значение символа хэш-карты в качестве текущего индекса символа.
d) Рассчитать end-start как самое длинное значение подстроки и обновить, если оно больше, чем самая длинная неповторяющаяся подстрока.
Ниже приведено решение Javascript для этой проблемы.
var lengthOfLongestSubstring = function(s) {
let length = s.length;
let ans = 0;
let start = 0,
end = 0;
let hashMap = {};
for (var i = 0; i < length; i++) {
if (!hashMap.hasOwnProperty(s[i])) {
hashMap[s[i]] = i;
} else {
if (start <= hashMap[s[i]]) {
start = hashMap[s[i]] + 1;
}
hashMap[s[i]] = i;
}
end++;
ans = ans > (end - start) ? ans : (end - start);
}
return ans;
};
Ответ 25
def max_substring(string):
last_substring = ''
max_substring = ''
for x in string:
k = find_index(x,last_substring)
last_substring = last_substring[(k+1):]+x
if len(last_substring) > len(max_substring):
max_substring = last_substring
return max_substring
def find_index(x, lst):
k = 0
while k <len(lst):
if lst[k] == x:
return k
k +=1
return -1
Ответ 26
Можем ли мы использовать что-то вроде этого.
def longestpalindrome(str1):
arr1=list(str1)
s=set(arr1)
arr2=list(s)
return len(arr2)
str1='abadef'
a=longestpalindrome(str1)
print(a)
если только длина подстроки должна быть возвращена
Ответ 27
Алгоритм:
1) Инициализируйте пустой словарь dct, чтобы проверить, существует ли какой-либо символ в строке.
2) cnt - вести подсчет подстроки без повторяющихся символов.
3) l и r - два указателя, инициализированные первым индексом строки.
4) перебрать каждый символ строки.
5) Если символ отсутствует в dct, добавьте его и увеличьте cnt.
6) Если он уже присутствует, проверьте, больше ли cnt, чем resStrLen.
7) Уберите символ из dct и сдвиньте левый указатель на 1 и уменьшите счет.
8) Повторите 5,6,7 до l, r больше или равно длине входной строки.
9) В конце сделайте еще одну проверку, чтобы обрабатывать такие случаи, как входная строка с неповторяющимися символами.
Вот простая программа на Python для поиска самой длинной подстроки без повторяющихся символов
a="stackoverflow"
strLength = len(a)
dct={}
resStrLen=0
cnt=0
l=0
r=0
strb=l
stre=l
while(l<strLength and r<strLength):
if a[l] in dct:
if cnt>resStrLen:
resStrLen=cnt
strb=r
stre=l
dct.pop(a[r])
cnt=cnt-1
r+=1
else:
cnt+=1
dct[a[l]]=1
l+=1
if cnt>resStrLen:
resStrLen=cnt
strb=r
stre=l
print "Result String Length : "+str(resStrLen)
print "Result String : " + a[strb:stre]
Ответ 28
Решение в С.
#include<stdio.h>
#include <string.h>
void longstr(char* a, int *start, int *last)
{
*start = *last = 0;
int visited[256];
for (int i = 0; i < 256; i++)
{
visited[i] = -1;
}
int max_len = 0;
int cur_len = 0;
int prev_index;
visited[a[0]] = 0;
for (int i = 1; i < strlen(a); i++)
{
prev_index = visited[a[i]];
if (prev_index == -1 || i - cur_len > prev_index)
{
cur_len++;
*last = i;
}
else
{
if (max_len < cur_len)
{
*start = *last - cur_len;
max_len = cur_len;
}
cur_len = i - prev_index;
}
visited[a[i]] = i;
}
if (max_len < cur_len)
{
*start = *last - cur_len;
max_len = cur_len;
}
}
int main()
{
char str[] = "ABDEFGABEF";
printf("The input string is %s \n", str);
int start, last;
longstr(str, &start, &last);
//printf("\n %d %d \n", start, last);
memmove(str, (str + start), last - start);
str[last] = '\0';
printf("the longest non-repeating character substring is %s", str);
return 0;
}
Ответ 29
public int lengthOfLongestSubstring(String s) {
int startIndex = 0;
int maxLength = 0;
//since we have 256 ascii chars
int[] lst = new int[256];
Arrays.fill(lst,-1);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
//to get ascii value of c
int ic = (int) c;
int value = lst[ic];
//this will say to move start index to next index of the repeating char
//we only do this if the repeating char index is greater than start index
if (value >= startIndex) {
maxLength = Math.max(maxLength, i - startIndex);
startIndex = value + 1;
}
lst[ic] = i;
}
//when we came to an end of string
return Math.max(maxLength,s.length()-startIndex);
}
Это самый быстрый и линейный время и постоянное пространство
Ответ 30
Я реализовал подобное решение в Java. Я возвращаю длину строки вместо всей строки.
Найдите ниже решение для ссылки:
public int getLengthOfLongestSubstring(String input) {
char[] chars = input.toCharArray();
String longestString = "";
String oldString="";
for(int i= 0; i < chars.length;i++) {
if (longestString.contains(String.valueOf(chars[i])))
{
if(longestString.length() > oldString.length()){
oldString = longestString;
}
if(longestString.split(String.valueOf(chars[i])).length>1)
longestString= longestString.split(String.valueOf(chars[i]))[1]+(chars[i]);
else{
longestString =String.valueOf(chars[i]);
}
}
else{
longestString =longestString+chars[i];
}
}
return oldString.length()< longestString.length()? longestString.length(): oldString.length();
}
Или можете использовать следующую ссылку в качестве ссылки.
Git URL
