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

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

本文概述

给定字符串, 请打印最长的子字符串, 而不重复字符。例如, 没有重复字符" ABDEFGABEF"的最长子串是" BDEFGA"和" DEFGAB", 长度为6。对于" BBBB", 最长子串是" B", 长度为1。所需的时间复杂度为O(n ), 其中n是字符串的长度。

先决条件：

最长子串的长度, 不重复字符

例子：

Input : lsbin
Output : EKSFORG

Input : 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 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;
   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)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: