# 算法设计：打印最长的子字符串而不重复字符

2021年3月12日13:29:34 发表评论 734 次浏览

## 本文概述

``````Input : lsbin
Output : EKSFORG

Input : ABDEFGABEF
Output : BDEFGA``````

## 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 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 = "lsbin"
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< char , int > pos = new Dictionary< char , int >();

// Last occurrence of first
// character is index 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]))
{
}
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)