打印最长的子字符串而不重复字符-yiteyi-C++库

给定一个字符串，打印不重复字符的最长子字符串。例如，“ABDEFGABEF”中没有重复字符的最长子字符串是“BDEFGA”和“DEFGAB”，长度为6。对于“BBBB”，最长的子串是“B”，长度为1。所需的时间复杂度为O（n），其中n是字符串的长度。 先决条件： 无重复字符的最长子字符串的长度 例如：

null

Input : GEEKSFORGEEKSOutput : EKSFORGInput : ABDEFGABEFOutput : BDEFGA

建议：请先在IDE上尝试您的方法，然后再查看解决方案。

方法： 其思想是遍历字符串，并将每个已访问的字符的最后一次出现存储在哈希表中（这里无序的_映射用作哈希，键作为字符，值作为其最后位置）。变量st存储当前子字符串的起始点，maxlen存储最大长度子字符串的长度，start存储最大长度子字符串的起始索引。遍历字符串时，检查哈希表中是否存在当前字符。如果不存在，则将当前字符存储在哈希表中，并将值作为当前索引。如果它已经存在于哈希表中，这意味着当前字符可以在当前子字符串中重复。对于该检查，如果字符的上一次出现在当前子字符串的起始点st之前或之后。如果在st之前，则只更新哈希表中的值。如果在st之后，则将当前子字符串curren的长度作为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 =                                     "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<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 =                                     "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<                                     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 =                                     "GEEKSFORGEEKS"                                     ;                       
                                                 Console.Write(findlongestSubstring(str));                       
                         }                       
                         }                       
           
                         // This code is contributed by shikhasingrajput                       

Javascript

                         <script>                       
           
                         // JavaScript program for the above approach                       
           
                         // Function to find and print longest                       
                         // substring without repeating characters.                       
                         function                                     findLongestSubstring(str)                       
                         {                       
                                                 var                                     i;                       
                                                 var                                     n = str.length;                       
           
                                                 // starting point of current substring.                       
                                                 var                                     st = 0;                       
           
                                                 // length of current substring.                       
                                                 var                                     currlen;                       
           
                                                 // maximum length substring without repeating                       
                                                 // characters.                       
                                                 var                                     maxlen = 0;                       
           
                                                 // starting index of maximum length substring.                       
                                                 var                                     start;                       
           
                                                 // Hash Map to store last occurrence of each                       
                                                 // already visited character.                       
                                                 var                                     pos =                                     new                                     Map();                       
           
                                                 // Last occurrence of first character is index 0;                       
                                                 pos.set(str[0], 0);                       
           
                                                 for                                     (                                     var                                     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.has(str[i]))                       
                                                 pos.set(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.get(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.get(str[i]) + 1;                       
                                                 }                       
           
                                                 // Update last occurrence of                       
                                                 // current character.                       
                                                 pos.set(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);                       
                         }                       
           
                         var                                     str =                                     "GEEKSFORGEEKS"                                     ;                       
                         document.write(findLongestSubstring(str));                       
           
                         // This code is contributed by SoumikMondal                       
           
                         </script>                       

输出：

EKSFORG

时间复杂性： O（n） 辅助空间： O（n）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章