原文：
给定一个字符串，打印最长的子字符串，而不重复字符。 例如，abdefgabef的没有重复字符的最长子串是bdefga和defgab，长度为 6。对于bbbb，最长子串是b，长度为 1。所需的时间复杂度为o(n)，其中n是字符串的长度。
先决条件：
示例：
input : geeksforgeeks
output : eksforg
input : abdefgabef
output : bdefga
方法：想法是遍历字符串，对于每个已访问的字符，将其最后一次出现存储在哈希表中（此处unordered_map用作哈希，键作为字符，值作为其最后位置）。 变量st存储当前子串的起点，maxlen存储最大长度子串的长度，start存储最大长度子串的起始索引。 在遍历字符串时，请检查哈希表中是否存在当前字符。 如果不存在，则将当前字符存储在哈希表中，并将值作为当前索引。 如果哈希表中已经存在该字符，则意味着当前字符可以在当前子字符串中重复。 对于此检查，字符的上一次出现是在当前子字符串的起点st之前还是之后。 如果它在st之前，则仅更新哈希表中的值。 如果在st之后，则找到当前子串currlen的长度为i - st，其中i是当前索引。 比较currlen和maxlen。 如果maxlen小于currlen，则将maxlen更新为currlen并从st开始。 完整遍历字符串后，所需的最长子字符串（不重复字符）为s[start]到s [start maxlen - 1]。
实现：
c
// c program to find and print longest
// substring without repeating characters.
#include
using namespace std;
// function to find and print longest
// substring without repeating characters.
string findlongestsubstring(string str)
{
int i;
int n = str.length();
// starting point of current substring.
int st = 0;
// length of current substring.
int currlen;
// maximum length substring without repeating
// characters.
int maxlen = 0;
// starting index of maximum length substring.
int start;
// hash map to store last occurrence of each
// already visited character.
unordered_map pos;
// last occurrence of first character is index 0;
pos[str[0]] = 0;
for (i = 1; i < n; i ) {
// if this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (pos.find(str[i]) == pos.end())
pos[str[i]] = i;
else {
// if this character is present in hash then
// this character has previous occurrence,
// check if that occurrence is before or after
// starting point of current substring.
if (pos[str[i]] >= st) {
// find length of current substring and
// update maxlen and start accordingly.
currlen = i - st;
if (maxlen < currlen) {
maxlen = currlen;
start = st;
}
// next substring will start after the last
// occurrence of current character to avoid
// its repetition.
st = pos[str[i]] 1;
}
// update last occurrence of
// current character.
pos[str[i]] = i;
}
}
// compare length of last substring with maxlen and
// update maxlen and start accordingly.
if (maxlen < i - st) {
maxlen = i - st;
start = st;
}
// the required longest substring without
// repeating characters is from str[start]
// to str[start maxlen-1].
return str.substr(start, maxlen);
}
// driver function
int main()
{
string str = "geeksforgeeks";
cout << findlongestsubstring(str);
return 0;
}
java
// java program to find
// and print longest substring
// without repeating characters.
import java.util.*;
class gfg{
// function to find and print longest
// substring without repeating characters.
public static string findlongestsubstring(string str)
{
int i;
int n = str.length();
// starting point
// of current substring.
int st = 0;
// length of
// current substring.
int currlen = 0;
// maximum length
// substring without
// repeating characters.
int maxlen = 0;
// starting index of
// maximum length substring.
int start = 0;
// hash map to store last
// occurrence of each
// already visited character.
hashmap pos = new hashmap();
// last occurrence of first
// character is index 0;
pos.put(str.charat(0), 0);
for (i = 1; i < n; i )
{
// if this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (!pos.containskey(str.charat(i)))
{
pos.put(str.charat(i), i);
}
else
{
// if this character is present
// in hash then this character
// has previous occurrence,
// check if that occurrence
// is before or after starting
// point of current substring.
if (pos.get(str.charat(i)) >= st)
{
// find length of current
// substring and update maxlen
// and start accordingly.
currlen = i - st;
if (maxlen < currlen)
{
maxlen = currlen;
start = st;
}
// next substring will start
// after the last occurrence
// of current character to avoid
// its repetition.
st = pos.get(str.charat(i)) 1;
}
// update last occurrence of
// current character.
pos.replace(str.charat(i), i);
}
}
// compare length of last
// substring with maxlen and
// update maxlen and start
// accordingly.
if (maxlen < i - st)
{
maxlen = i - st;
start = st;
}
// the required longest
// substring without
// repeating characters
// is from str[start]
// to str[start maxlen-1].
return str.substring(start,
start
maxlen);
}
// driver code
public static void main(string[] args)
{
string str = "geeksforgeeks";
system.out.print(findlongestsubstring(str));
}
}
// this code is contributed by divyeshrabadiya07
python3
# python3 program to find and print longest
# substring without repeating characters.
# function to find and print longest
# substring without repeating characters.
def findlongestsubstring(string):
n = len(string)
# starting point of current substring.
st = 0
# maximum length substring without
# repeating characters.
maxlen = 0
# starting index of maximum
# length substring.
start = 0
# hash map to store last occurrence
# of each already visited character.
pos = {}
# last occurrence of first
# character is index 0
pos[string[0]] = 0
for i in range(1, n):
# if this character is not present in hash,
# then this is first occurrence of this
# character, store this in hash.
if string[i] not in pos:
pos[string[i]] = i
else:
# if this character is present in hash then
# this character has previous occurrence,
# check if that occurrence is before or after
# starting point of current substring.
if pos[string[i]] >= st:
# find length of current substring and
# update maxlen and start accordingly.
currlen = i - st
if maxlen < currlen:
maxlen = currlen
start = st
# next substring will start after the last
# occurrence of current character to avoid
# its repetition.
st = pos[string[i]] 1
# update last occurrence of
# current character.
pos[string[i]] = i
# compare length of last substring with maxlen
# and update maxlen and start accordingly.
if maxlen < i - st:
maxlen = i - st
start = st
# the required longest substring without
# repeating characters is from string[start]
# to string[start maxlen-1].
return string[start : start maxlen]
# driver code
if __name__ == "__main__":
string = "geeksforgeeks"
print(findlongestsubstring(string))
# this code is contributed by rituraj jain
c
// c# program to find
// and print longest substring
// without repeating characters.
using system;
using system.collections.generic;
class gfg{
// function to find and
// print longest substring
// without repeating characters.
public static string findlongestsubstring(string str)
{
int i;
int n = str.length;
// starting point
// of current substring.
int st = 0;
// length of
// current substring.
int currlen = 0;
// maximum length
// substring without
// repeating characters.
int maxlen = 0;
// starting index of
// maximum length substring.
int start = 0;
// hash map to store last
// occurrence of each
// already visited character.
dictionary pos = new dictionary();
// last occurrence of first
// character is index 0;
pos.add(str[0], 0);
for (i = 1; i < n; i )
{
// if this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (!pos.containskey(str[i]))
{
pos.add(str[i], i);
}
else
{
// if this character is present
// in hash then this character
// has previous occurrence,
// check if that occurrence
// is before or after starting
// point of current substring.
if (pos[str[i]] >= st)
{
// find length of current
// substring and update maxlen
// and start accordingly.
currlen = i - st;
if (maxlen < currlen)
{
maxlen = currlen;
start = st;
}
// next substring will start
// after the last occurrence
// of current character to avoid
// its repetition.
st = pos[str[i]] 1;
}
// update last occurrence of
// current character.
pos[str[i]] = i;
}
}
// compare length of last
// substring with maxlen and
// update maxlen and start
// accordingly.
if (maxlen < i - st)
{
maxlen = i - st;
start = st;
}
// the required longest
// substring without
// repeating characters
// is from str[start]
// to str[start maxlen-1].
return str.substring(start,
maxlen);
}
// driver code
public static void main(string[] args)
{
string str = "geeksforgeeks";
console.write(findlongestsubstring(str));
}
}
// this code is contributed by shikhasingrajput
输出：
eksforg
时间复杂度：o(n)。
辅助空间：o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
