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

Question

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

Пример:

Ввод:"stackoverflow"

Вывод:"stackoverfl"

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

Answer 1

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

2. Начало в начале строки, оба локатора указывают на начало строки.

3. Перемещайте указатель конца вправо, пока не найдете повторение (или достичь конца строки). Для каждого обработанного символа сохраните его в массиве. Когда остановлено, сохраните позицию, если это самая большая подстрока. Также запомните повторный символ.

4. Теперь сделайте то же самое с локатором запуска при обработке каждый символ, удалите его флаги из массива. Переместить локатор до Вы обнаружите более раннее вхождение повторяющегося символа.

5. Вернитесь к шагу 3, если вы не достигли конца строки.

Общий рейтинг: O (N)

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

Answer 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]

Answer 4

Вот еще одно решение с двумя строковыми переменными:

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

Answer 5

РЕДАКТИРОВАНИЕ:

Ниже приводится реализация концепции.Это произошло со мной после моей оригинальной публикации.чтобы не удалять оригинал, представляется следующее:

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

ОРИГИНАЛЬНАЯ ПОЧТА:

Вот мои два цента.Тестовые строки включены.логические биты [] = новый логический [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]));
    }
}

Answer 6

Мы можем рассмотреть все подстроки одну за другой и проверить для каждой подстроки, содержит ли она все уникальные символы или нет. Там будет n * (n + 1) / 2 подстроки. Содержит ли substirng все уникальные символы или нет, можно проверить за линейное время сканирование его слева направо и ведение карты посещенных персонажей. Временная сложность этого решения будет 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;
}
}

Answer 7

Алгоритм в 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's 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

Answer 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>

Answer 9

простой фрагмент Python l = длина p = позиция maxl = maxlength maxp = maxposition

Answer 10

Эта проблема может быть решена за O (n) временной сложности. Инициализируйте три переменные

1. Start (индекс указывает на начало неповторяющейся подстроки, Инициализируйте его как 0).
2. Конец (индекс указывает на конец неповторяющейся подстроки, Инициализируйте его как 0)
3. Hasmap (Объект, содержащий последние посещенные позиции индекса символов. Например: {'a': 0, 'b': 1} для строки "ab")

шаги: Выполните итерацию по строке и выполните следующие действия.

1. Если текущий символ отсутствует в hashmap (), добавьте его как hashmap, символ в качестве ключа и его индекс в качестве значения.

2. Если текущий символ присутствует в hashmap, тогда

   a) Проверить, меньше или равен стартовый индекс значению, присутствующему в хэш-карте для символа (последний индекс того же символа, который был ранее),

   b) меньше значения начальных переменных присваивать как значение хеш-карт + 1 (последний посещенный ранее индекс того же символа + 1);

   в) Обновите хэш-карту, переопределив текущее значение символа хеш-карты в качестве текущего индекса символа.

   d) Рассчитать начало конца как самое длинное значение подстроки и обновить, если оно больше, чем самая длинная неповторяющаяся подстрока.

Ниже приведено решение 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;
};