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


  • 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;

}

};