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

Question

Учитывая string S из length N найти самую длинную подстроку без повторяющихся символов.

Пример:

Ввод:"stackoverflow"

Вывод:"stackoverfl"

Если есть два таких кандидата, вернитесь сначала слева.Мне нужен алгоритм линейного времени и постоянного пространства.

Answer 1

просто и легко

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();
    }

}

Answer 2

Я публикую 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()

Answer 3

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

Answer 4

вот мои реализации 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], подстрока может продолжать расти.

Answer 5

мы можем использовать что-то вроде этого.

def longestpalindrome(str1):
    arr1=list(str1)
    s=set(arr1)
    arr2=list(s)
    return len(arr2)



str1='abadef'
a=longestpalindrome(str1)
print(a)

если возвращается только длина подстроки

Answer 6

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));
    }
}

Answer 7

Раствор в кл.

#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;
}

Answer 8

Я изменил свое решение, чтобы «найти длину самой длинной подстроки без повторяющихся символов».

        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);
}

Answer 9

Я реализовал подобное решение в 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

Answer 10

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();
    }
}