Python 中最长无重复字符的子字符串

pythonserver side programmingprogramming更新于 2025/10/25 10:52:17

假设我们有一个字符串。我们必须找到最长的无重复字符的子字符串。因此，如果字符串类似于"ABCABCBB"，则结果将为 3，因为有一个重复的子字符串，长度为 3。即"ABC"。

为了解决这个问题，我们将遵循以下步骤

设置 i := 0, j := 0，设置一个映射来存储信息
ans := 0
当 j < 字符串 s 的长度
- 如果 s[j] 不在映射中，或 i > map[s[j]]，则
  - ans := max(ans, j – i + 1)
  - map[s[j]] := j
- 否则
  - i := map[s[j]] + 1
  - ans := max(ans, j – i + 1)
  - 将 j 减少 1
- 将 j 增加 1
返回 ans

示例 (Python)

让我们看看以下实现以便更好地理解

class Solution(object):
   def lengthOfLongestSubstring(self, s):
      i =0
      j = 0
      d={}
      ans = 0
      while j < len(s):
         if s[j] not in d or i>d[s[j]]:
            ans = max(ans,(j-i+1))
            d[s[j]] = j
         else:
            i = d[s[j]]+1
            ans = max(ans,(j-i+1))
            j-=1
         #print(ans)
         j+=1
      return ans
ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))