424. Longest Repeating Character Replacement (Medium)

https://leetcode.com/problems/longest-repeating-character-replacement/

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Solutions

class Solution {
    // To get longest repeating character replacement, we need to sort out substrings that
    // consists of k + 1 unique characters. Then replace those of low frequence.

    public int characterReplacement(String s, int k) {
        Set<Character> letters = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            letters.add(s.charAt(i));
        }

        int max = 0;
        for (Character c : letters) {
            // count for current character
            int count1 = 0;

            // count for other character
            int count2 = 0;

            // left and right pointer
            int lptr = 0;
            int rptr = 0;

            while(true) {
                if (s.charAt(rptr) == c) {
                    count1++;
                } else {
                    count2++;
                }

                // update the max len of repeating characters if possible
                if (count2 == k && count1 + count2 > max) {
                    max = count1 + count2;
                }

                // It's allowed to replace only at most k elements. Once exceeds this limit,
                // prune the window from left, remove the head char.
                while(count2 > k) {
                    if (s.charAt(lptr) == c) {
                        count1--;
                    } else {
                        count2--;
                    }

                    lptr++;
                }

                // rptr must not overstep the boundary of s
                if (rptr == s.length()-1) {
                    // before break the loop, check out the last subsequence
                    if (count1 + count2 > max) {
                        max = count1 + count2;
                    }

                    break;
                }

                rptr++;
            }
        }

        return max;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""