首页 > 其他 > 详细

LeetCode 1156. Swap For Longest Repeated Character Substring

时间:2019-12-08 10:55:32      阅读:149      评论:0      收藏:0      [点我收藏+]

原题链接在这里:https://leetcode.com/problems/swap-for-longest-repeated-character-substring/

题目:

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first ‘b‘ with the last ‘a‘, or the last ‘b‘ with the first ‘a‘. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap ‘b‘ with the last ‘a‘ (or the first ‘a‘), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:

Input: text = "aaabbaaa"
Output: 4

Example 4:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:

Input: text = "abcdef"
Output: 1

Constraints:

  • 1 <= text.length <= 20000
  • text consist of lowercase English characters only.

题解:

There could be 2 cases to achieve the fulfilled longest substring.

case 1: One block containing longest. And then replace one boundary char to be the same, and get len+1.

case 2: Two blocks containing same chars separated by 1 single different char. In this case, the single different char could be replaced.

Both cases, it needs to make sure that there are extra same chars.

Time Complexity: O(n). n = text.length.

Space: O(n).

AC Java:

 1 class Solution {
 2     public int maxRepOpt1(String text) {
 3         if(text == null || text.length() == 0){
 4             return 0;
 5         }
 6         
 7         int len = text.length();
 8         int [] map = new int[26];
 9         List<Pair> groupsList = new ArrayList<>();
10         int i = 0;
11         
12         while(i < len){
13             char c = text.charAt(i);
14             int f = 0;
15             while(i < len && text.charAt(i) == c){
16                 f++;
17                 i++;
18             }
19             
20             groupsList.add(new Pair(c, f));
21             map[c-‘a‘] += f;
22         }
23         
24         int max = 0;
25         for(int j = 0; j<groupsList.size(); j++){
26             Pair cur = groupsList.get(j);
27             
28             // Single group
29             max = Math.max(max, Math.min(cur.f+1, map[cur.c - ‘a‘]));
30             
31             // Two groups
32             if(j < groupsList.size() - 2){
33                 if(groupsList.get(j+1).f == 1 && cur.c == groupsList.get(j+2).c){
34                     max = Math.max(max, Math.min(cur.f + groupsList.get(j+2).f + 1, map[cur.c - ‘a‘]));
35                 }
36             }
37         }
38         
39         return max;
40     }
41 }
42 
43 class Pair{
44     char c;
45     int f;
46     public Pair(char c, int f){
47         this.c = c;
48         this.f = f;
49     }
50 }

 

LeetCode 1156. Swap For Longest Repeated Character Substring

原文:https://www.cnblogs.com/Dylan-Java-NYC/p/12004508.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!