找到最长的子字符串而不重复字符

Question

给定string S的length N找到最长子不重复的字符.

例:

输入: "stackoverflow"

输出: "stackoverfl"

如果有两个这样的候选人,请先从左边返回.我需要线性时间和恒定空间算法.

Answer 1

1. 您将需要字符串的开始和结束定位器(/指针)以及存储每个字符的信息的数组:它是否至少出现一次？

2. 从字符串的开头开始,两个定位器都指向字符串的开头.

3. 将结束定位器向右移动,直到找到重复(或到达字符串的末尾).对于每个已处理的字符,将其存储在数组中.如果这是最大的子字符串,则停止存储位置.还要记住重复的角色.

4. 现在使用start locator做同样的事情,处理每个字符时,从数组中删除它的标志.移动定位器,直到找到重复字符的早期出现.

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]