In this post we will solve the LeetCode 1156. Swap For Longest Repeated Character Substring problem using the Java programming language.
You are given a string text. You can swap two of the characters in the text. Return the length of the longest substring with repeated characters. Constraints: o 1 <= text.length <= 2 * 10^4 o text consist of lowercase English characters only. Related Topics: o String o Sliding Window
We are given a string of English lowercase characters and we can swap two characters once in order to return the longest count of consecutive characters.
If interested in this problem please go to the LeetCode website and read the current description of the problem in case it has been updated.
public int maxRepOpt1(String text) {
}
The signature of the function states that we are just given the input string and we need to return the longest count of consecutive characters after we swap two characters.
After thinking and coming up with an approach the simplest way to solve the problem is to use the online IDE provided by LeetCode. I will be solving the problem on a Windows computer and when reasonable will copy the solution to the LeetCode site in order to submit it for evaluation. Such an approach allows me to keep the test code and the solution in the same source file. The test code that we will write IS NOT PART OF THE SOLUTION!
ababa main <<< text ==>ababa<== <<< len: 5 <<< arr: [a, b, a, b, a] <<< freqs: [3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [1, 1, 1, 1, 1] <<< arr[0]: a arr[1]: b arr[2]: a <<< [2] count: 2 <<< [3] count: 3 <<< maxLen: 3 <<< arr[1]: b arr[2]: a arr[3]: b <<< [2] count: 2 <<< [3] count: 2 <<< maxLen: 3 <<< arr[2]: a arr[3]: b arr[4]: a <<< [2] count: 2 <<< [3] count: 3 <<< maxLen: 3 <<< arr[3]: b arr[4]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 3 <<< [4] count: 2 main <<< maxRepOpt1: 3 aaabaaa main <<< text ==>aaabaaa<== <<< len: 7 <<< arr: [a, a, a, b, a, a, a] <<< freqs: [6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [3, 2, 1, 1, 3, 2, 1] <<< arr[0]: a arr[1]: a arr[2]: a <<< [1] count: 2 <<< arr[1]: a arr[2]: a arr[3]: b <<< [1] count: 3 <<< arr[2]: a arr[3]: b arr[4]: a <<< [2] count: 6 <<< [3] count: 6 <<< maxLen: 6 <<< arr[3]: b arr[4]: a arr[5]: a <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 6 <<< arr[4]: a arr[5]: a arr[6]: a <<< [1] count: 2 <<< arr[5]: a arr[6]: a <<< [1] count: 3 <<< [4] count: 4 main <<< maxRepOpt1: 6 aaabbaaa main <<< text ==>aaabbaaa<== <<< len: 8 <<< arr: [a, a, a, b, b, a, a, a] <<< freqs: [6, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [3, 2, 1, 2, 1, 3, 2, 1] <<< arr[0]: a arr[1]: a arr[2]: a <<< [1] count: 2 <<< arr[1]: a arr[2]: a arr[3]: b <<< [1] count: 3 <<< arr[2]: a arr[3]: b arr[4]: b <<< [2] count: 3 <<< [3] count: 4 <<< maxLen: 4 <<< arr[3]: b arr[4]: b arr[5]: a <<< [1] count: 2 <<< arr[4]: b arr[5]: a arr[6]: a <<< [2] count: 2 <<< [3] count: 2 <<< maxLen: 4 <<< arr[5]: a arr[6]: a arr[7]: a <<< [1] count: 2 <<< arr[6]: a arr[7]: a <<< [1] count: 3 <<< [4] count: 4 main <<< maxRepOpt1: 4 aaaaa main <<< text ==>aaaaa<== <<< len: 5 <<< arr: [a, a, a, a, a] <<< freqs: [5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [5, 4, 3, 2, 1] <<< arr[0]: a arr[1]: a arr[2]: a <<< [1] count: 2 <<< arr[1]: a arr[2]: a arr[3]: a <<< [1] count: 3 <<< arr[2]: a arr[3]: a arr[4]: a <<< [1] count: 4 <<< arr[3]: a arr[4]: a <<< [1] count: 5 main <<< maxRepOpt1: 5 abcde main <<< text ==>abcde<== <<< len: 5 <<< arr: [a, b, c, d, e] <<< freqs: [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [1, 1, 1, 1, 1] <<< arr[0]: a arr[1]: b arr[2]: c <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 1 <<< arr[1]: b arr[2]: c arr[3]: d <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 1 <<< arr[2]: c arr[3]: d arr[4]: e <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 1 <<< arr[3]: d arr[4]: e <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 1 main <<< maxRepOpt1: 1 abcabcabca main <<< text ==>abcabcabca<== <<< len: 10 <<< arr: [a, b, c, a, b, c, a, b, c, a] <<< freqs: [4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] <<< arr[0]: a arr[1]: b arr[2]: c <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[1]: b arr[2]: c arr[3]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[2]: c arr[3]: a arr[4]: b <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[3]: a arr[4]: b arr[5]: c <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[4]: b arr[5]: c arr[6]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[5]: c arr[6]: a arr[7]: b <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[6]: a arr[7]: b arr[8]: c <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[7]: b arr[8]: c arr[9]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[8]: c arr[9]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< [4] count: 2 main <<< maxRepOpt1: 2 aabaabaaa main <<< text ==>aabaabaaa<== <<< len: 9 <<< arr: [a, a, b, a, a, b, a, a, a] <<< freqs: [7, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [2, 1, 1, 2, 1, 1, 3, 2, 1] <<< arr[0]: a arr[1]: a arr[2]: b <<< [1] count: 2 <<< arr[1]: a arr[2]: b arr[3]: a <<< [2] count: 4 <<< [3] count: 5 <<< maxLen: 5 <<< arr[2]: b arr[3]: a arr[4]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 5 <<< arr[3]: a arr[4]: a arr[5]: b <<< [1] count: 2 <<< arr[4]: a arr[5]: b arr[6]: a <<< [2] count: 5 <<< [3] count: 6 <<< maxLen: 6 <<< arr[5]: b arr[6]: a arr[7]: a <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 6 <<< arr[6]: a arr[7]: a arr[8]: a <<< [1] count: 2 <<< arr[7]: a arr[8]: a <<< [1] count: 3 <<< [4] count: 4 main <<< maxRepOpt1: 6 aaba main <<< text ==>aaba<== <<< len: 4 <<< arr: [a, a, b, a] <<< freqs: [3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [2, 1, 1, 1] <<< arr[0]: a arr[1]: a arr[2]: b <<< [1] count: 2 <<< arr[1]: a arr[2]: b arr[3]: a <<< [2] count: 3 <<< [3] count: 3 <<< maxLen: 3 <<< arr[2]: b arr[3]: a <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 3 <<< [4] count: 2 main <<< maxRepOpt1: 3 acbaaa main <<< text ==>acbaaa<== <<< len: 6 <<< arr: [a, c, b, a, a, a] <<< freqs: [4, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< right: [1, 1, 1, 3, 2, 1] <<< arr[0]: a arr[1]: c arr[2]: b <<< [2] count: 1 <<< [3] count: 2 <<< maxLen: 2 <<< arr[1]: c arr[2]: b arr[3]: a <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 2 <<< arr[2]: b arr[3]: a arr[4]: a <<< [2] count: 1 <<< [3] count: 1 <<< maxLen: 2 <<< arr[3]: a arr[4]: a arr[5]: a <<< [1] count: 2 <<< arr[4]: a arr[5]: a <<< [1] count: 3 <<< [4] count: 4 main <<< maxRepOpt1: 4
Each test case is separated by two blank lines.
The first line of each test case contains the input string. Our test scaffold seems to read the input line, populate a string and display its contents to make sure all is well so far.
The function of interest is then called. The intermediate lines are displayed in order to verify that the code is executing as expected. They are NOT PART OF THE SOLUTION.
The last line of each test case contains the answer. Given the problem description it is quite simple to verify in each of the test cases if the result is correct or not.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read input string ****
String text = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< text ==>" + text + "<==");
// **** call function of interest and display result ****
// System.out.println("main <<< maxRepOpt10: " + maxRepOpt10(text));
// **** call function of interest and display result ****
System.out.println("main <<< maxRepOpt1: " + maxRepOpt1(text));
}
The test scaffold IS NOT PART OF THE SOLUTION!
It reads the input line, displays the contents of the string, calls the function of interest and displays the maximum number of consecutive characters.
We will use a sliding window approach in our solution.
/**
* Return the length of the longest substring with repeated characters.
*
* Execution: O(n) - Space: O(2 * dn + K)
*
* Runtime: 6 ms, faster than 68.45% of Java online submissions.
* Memory Usage: 39.5 MB, less than 14.44% of Java online submissions.
*
* 56 / 56 test cases passed.
* Status: Accepted
* Runtime: 6 ms
* Memory Usage: 39.5 MB
*/
static public int maxRepOpt1(String text) {
// **** sanity check(s) ****
int len = text.length();
if (len == 1) return 1;
// ???? ????
System.out.println("<<< len: " + len);
// **** initialization ****
int count = 1;
int maxLen = 1;
char[] arr = text.toCharArray();
int [] freqs = new int[26];
int [] right = new int [len];
// **** populate the right and freqs arrays ****
for (int i = len - 1; i >= 0; i--) {
freqs[arr[i] - 'a']++;
right[i] = 1 + ((i + 1 < len && arr[i + 1] == arr[i]) ? right[i + 1] : 0);
}
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
System.out.println("<<< freqs: " + Arrays.toString(freqs));
System.out.println("<<< right: " + Arrays.toString(right));
// **** traverse the arr[] left to right ****
for (int i = 1; i < len; i++) {
// ???? ????
System.out.print( "<<< arr[" + (i - 1) + "]: " + arr[i - 1] +
" arr[" + i + "]: " + arr[i]);
if (i < len - 1)
System.out.print(" arr[" + (i + 1) + "]: " + arr[i + 1]);
System.out.println();
// **** check if same consecutive characters ****
if (arr[i - 1] == arr[i]) {
// **** increment count ****
count++;
// ???? ????
System.out.println("<<< [1] count: " + count);
}
// **** different consecutive characters ****
else {
// **** check if previous is equal to next character ****
count = count + ((i + 1 < len && arr[i - 1] == arr[i + 1]) ? right[i + 1] : 0);
// ???? ????
System.out.println("<<< [2] count: " + count);
// **** check if current character may be replaced ****
if (freqs[arr[i - 1] - 'a'] > count) count += 1;
// ???? ????
System.out.println("<<< [3] count: " + count);
// **** update maximum length of consecutive characters ****
maxLen = Math.max(maxLen, count);
// ???? ????
System.out.println("<<< maxLen: " + maxLen);
// **** reset counter ****
count = 1;
}
}
// **** check last character in the string ****
if (freqs[arr[len - 1] - 'a'] > count) {
// **** increment counter ****
count += 1;
// ???? ????
System.out.println("<<< [4] count: " + count);
}
// **** return max length or count ****
return Math.max(maxLen, count);
}
We start by performing a sanity check.
We then initialize some variables and populate some arrays.
The arr[] contains the characters from the input string. This should speed up repeatedly finding individual characters in the input string. The freqs[] array holds the frequencies of each character in the input string. I could have used a Hash Map but they tend to be slower and incur in additional space when compared by a character array. The right[] contains the counts of each character when traversing the string starting at the right side.
The first loop is used to simultaneously populate the freqs[] and right[] arrays. We could have done it using two separate loops.
The main loop implements a sliding window that starts on the second character in the string. The window has a width of three characters until it hits the first to last character.
The code is split into two conditions. If the previous character matches the current character we just add one to the `count` of repeated characters. Otherwise, we perform a set of steps that update the `count` using the sliding window contents, the right[] and the freqs[] arrays and the `maxLen` variable which holds the maximum length of repeated characters so far. Note that the `count` is set to one in order to repeat the counting process of the loop.
After the loop completes, we need to take care of the last character in the string since it was not processed in the loop.
Our function returns the value of the `maxLen` or `count`.
Sorry about all the `println` statements. They ARE NOT PART OF THE SOLUTION, but they allow us to follow the execution and determine if all is working as expected.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named SwapForLongestRepeatedCharSubstring.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John