hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Determine if String Halves Are Alike
Problem: 1704. Determine if String Halves Are Alike
Problem Link: https://leetcode.com/problems/determine-if-string-halves-are-alike/
Approach:
Sharing two different approaches along with codes below.
Time and Space Complexity:
Time complexity: O(n)
Space complexity: O(1)
Code [C++] | O(N) Time and O(N) Space
Increased the vowel count in an array called count_vowels. And check if the count of vowels is equal if we cut the count_vowels array in equal half size.
class Solution {
public:
bool halvesAreAlike(string s) {
int n = s.size();
vector<int>count_vowels(n, 0);
for(int i=0; i<n; i++){
char ith_ch = tolower(s[i]);
if(i) count_vowels[i] = count_vowels[i-1];
if(ith_ch == 'a' || ith_ch == 'e' || ith_ch == 'i' || ith_ch == 'o' || ith_ch == 'u'){
count_vowels[i]++;
}
}
return count_vowels[n/2 - 1] == (count_vowels[n-1] - count_vowels[n/2 - 1]);
}
};
Code [C++] | O(N) Time and O(1) Space
Increased the counter of vowels if the vowel is situated at the left half of the array. Decreased otherwise. Checked if the count_vowels is 0 or not.
class Solution {
public:
bool halvesAreAlike(string s) {
int n = s.size();
int count_vowels = 0;
for(int i=0; i<n; i++){
char ith_ch = tolower(s[i]);
if(ith_ch == 'a' || ith_ch == 'e' || ith_ch == 'i' || ith_ch == 'o' || ith_ch == 'u'){
count_vowels += (i < n/2) ? 1 : - 1;
}
}
return !count_vowels;
}
};