文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

描述
給你一個(gè)只由字母’A’和’B’組成的字符串s，找一個(gè)最長的子串，要求這個(gè)子串里面’A’和’B’的數(shù)目相等，輸出該子串的長度。

這個(gè)子串可以為空。 s的長度n滿足 2<=n<=1000000。示例 樣例1 輸入: s = "ABAAABBBA" 輸出: 8 解釋: 子串 s[0,7] 和子串 s[1,8] 滿足條件，長度為 8。樣例2 輸入: s = "AAAAAA" 輸出: 0 解釋: s 中除了空字串，不存在 'A' 和 'B' 數(shù)目相等的子串。

https://tianchi.aliyun.com/oj/496421179568411239/552131449257661029

2. 解題

• 遇到 A +1， 遇到 B -1，同時(shí)將沒有出現(xiàn)過的值存入哈希，若哈希中存在某一值，則中間的AB個(gè)數(shù)相等

class Solution { public:/*** @param S: a String consists of a and b* @return: the longest of the longest string that meets the condition*/int getAns(string &s) {// Write your code hereunordered_map<int,int> m;m[0] = -1;int sum = 0, ans = 0;for(int i = 0; i < s.size(); ++i){if(s[i] =='A')sum++;elsesum--;if(m.find(sum) != m.end())ans = max(ans, i-m[sum]);elsem[sum] = i;}return ans;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的天池 在线编程 最长AB子串（哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。