Created
August 28, 2021 22:03
-
-
Save keif/09d28c492a4b59c429cfbea4f9ae3f94 to your computer and use it in GitHub Desktop.
Given a string, find the maximum consecutive repeating character in itself.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// given a string, give me the count of each particular character in the string. | |
// Hard mode: Give me the letter which is repeated the most in a row, regardless of how often the character appears in the string. | |
// “aaabbc” would return “a” | |
// “aaabbbbc” would return “b” | |
// “aaabbbbaacc” would return “b” | |
// “abababababcccababababababab” would return “c” | |
let strArr = [ | |
`aaabbc`, // a | |
`aaabbbbc`, // b | |
`aaabbbbaacc`, // b | |
`abababababcccacacacacacacac`, // c | |
] | |
// complexity: 0(n^2) (two for loops) | |
// | |
const maxRepeatingChar_twoForLoops = (str) => { | |
let len = str.length | |
let max_count = 0 | |
// Find the maximum repeating character | |
// starting from str[i] | |
let res = str[0] | |
for (let i = 0; i < len; i++) { | |
// start with our first character | |
let cur_count = 1 | |
for (let j = i + 1; j < len; j++) { | |
// if our characrers don't match, break out | |
if (str[i] != str[j]) { | |
break | |
} | |
// matched - increase | |
cur_count++ | |
} | |
// Update result if required | |
if (cur_count > max_count) { | |
max_count = cur_count | |
res = str[i] | |
} | |
} | |
return res | |
} | |
const maxRepeatingChar_singleForLoop = (str) => { | |
const n = str.length | |
let max_count = 0 | |
let res = str[0] | |
let cur_count = 1 | |
// Traverse string except last character | |
for (let i = 0; i < n; i++) { | |
// If current character matches with next | |
if (i < n - 1 && str[i] == str[i + 1]) { | |
cur_count++ | |
// If doesn't match, update result | |
// (if required) and reset count | |
} else { | |
if (cur_count > count) { | |
max_count = cur_count | |
res = str[i] | |
} | |
cur_count = 1 | |
} | |
} | |
return res | |
} | |
// loop through test data | |
console.time(`two for loops`) | |
strArr.forEach((str) => { | |
const res = maxRepeatingChar_twoForLoops(str) | |
console.log(res) | |
}) | |
console.timeEnd(`two for loops`); | |
console.time(`single for loop`) | |
strArr.forEach((str) => { | |
const res = maxRepeatingChar_singleForLoop(str) | |
console.log(res) | |
}) | |
console.timeEnd(`single for loop`); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment