本文概述

• C ++
• Java
• Python3
• C#

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

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 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)

推荐阅读

• 

  什么是职场？
• 

  百日练，一百天读一百本书，打卡第9天，《你只是看上去很努力》35分钟，理解50%，2000/分钟
• 

  空调主机跟遥控器显示温度不同步是怎么回事 新科柜机空调不制冷调节温度显示不同步
• 

  等闲识得东风面中的东风是什么意思 等闲识得东风面释义
• 

  redis 集合的底层实现 redis集合存bean
• 

  Java中关于Collections集合工具类的详细介绍
• 

  福州贵安水世界好玩吗 2023福州贵安水世界门票多少钱一张
• 

  蜗居背景音乐歌词蜗居背景音乐歌词翻译
• 

  甘肃所有大学名单 甘肃省大学排名
• 

  雷殿生名字打分99分 雷王姓取名
• 

  python|python 的生产者和消费者模式
• 

  quiet怎么读 quiet怎么造句
• 

  龙眼肉罐头做法 新鲜的龙眼肉怎么做罐头
• 

  海藻面膜敷多长时间好
• 

  mysql my.cnf配置模板参考
• 

  苹果扣费怎么退 iPhone扣费怎么退款
• 

  你认为孤独的根源是什么？
• 

  减肥期间,有哪些做起来简单又好吃的减肥食谱？
• 

  创维55寸4k智能电视多少钱一台 哪个电视牌子好
• 

  二甲双胍|糖尿病天天吃二甲双胍，请花5分钟弄清这6个注意事项，很重要

• 计算从mXn矩阵的左上到右下的所有可能路径
• Python如何将字典作为关键字参数传递（示例）
• 如何在JavaScript中实现消除抖动（代码实现示例）
• PHP常量用法详细教程和代码示例
• JavaScript中的多维数组用法指南
• OOP编程（Java中的继承详细指南）
• 多线程中的Java线程优先级介绍和代码实例
• 二叉树的枚举解析和算法实现原理
• 神经网络|完整的动手指南，可在Google Colab GPU上训练你的神经网络模型