本文概述
- C ++
- Java
- Python3
- C#
先决条件：
最长子串的长度, 不重复字符
例子：
Input : lsbin
Output : EKSFORGInput : ABDEFGABEF
Output : BDEFGA【算法设计（打印最长的子字符串而不重复字符）】推荐：请首先在IDE上尝试你的方法, 然后查看解决方案。
方法：
这个想法是遍历字符串, 并且对于每个已经访问过的字符, 将其最后一次出现存储在哈希表中(此处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 <
bits/stdc++.h>
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<
char , int >
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 = "lsbin" ;
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<
Character, Integer>
pos = new HashMap<
Character, Integer>
();
// 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 = "lsbin" ;
System.out.print(findLongestSubstring(str));
}
}
// This code is contributed by divyeshrabadiya07Python3
# 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 = "lsbin"
print (findLongestSubstring(string))
# This code is contributed by Rituraj JainC#
// 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<
char , int >
pos = new Dictionary<
char , int >
();
// 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 = "lsbin" ;
Console.Write(findlongestSubstring(str));
}
}
// This code is contributed by shikhasingrajput输出如下：
EKSFORG时间复杂度：
O(n)
辅助空间：
O(n)
推荐阅读
- 计算从mXn矩阵的左上到右下的所有可能路径
- Python如何将字典作为关键字参数传递（示例）
- 如何在JavaScript中实现消除抖动（代码实现示例）
- PHP常量用法详细教程和代码示例
- JavaScript中的多维数组用法指南
- OOP编程（Java中的继承详细指南）
- 多线程中的Java线程优先级介绍和代码实例
- 二叉树的枚举解析和算法实现原理
- 神经网络|完整的动手指南，可在Google Colab GPU上训练你的神经网络模型