Swift Leetcode Series: Determining if two String halves are alive

April Leetcoding Challenge 2021: Day 7

Determine if String Halves Are Alike (Leetcode 1704 ) -

If you are unable to view the story you can also read the full story on The Swift Nerd blog with the link above.

This problem was taken from April Leetcoding Challenge April 2021 on Leetcode. The solution discussed here is in Swift but you can use the approach in any language.

Problem Description

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

Example 3:

Input: s = "MerryChristmas"
Output: false

Example 4:

Input: s = "AbCdEfGh"
Output: true

Constraints

• 2 <= s.length <= 1000
• s.length is even.
• s consists of uppercase and lowercase letters.

Solution

One thing that comes into find is that we would be checking the counts of the vowels. We can use any collection like an array or dictionary to check since vowels are limited are not much so it is constant time. Also, we should either add both lowercase and uppercase vowels or we can add only the lowercase and while comparing we check the lowercased() character in the collection.

So, to keep things tidy, we will make a utility function to check if a character is a vowel and return true if it matches in any vowel in the collection while lowercase comparison.

Now the only thing remains is to check for the two string halves. The first idea comes to mind is that We can split the string in two parts using string.prefix(length/2) and string.suffix(length/2) and compare counts on both of the substrings, but we can do it without splitting the string as well.

Algodaily.com

Since it is given that length of the string is even, we can use the two-pointer approach to traverse the string. The low variable would iterate on first half and high variable can iterate on the second half. We can keep a counter variable and add 1 if character in first half is a vowel and decrease 1 if character in the other half satisfies the condition. The idea is that if vowel counts in both parts of the string is same , then they would balance out and their difference should be 0. In Swift, random access on Strings are not allowed so we can convert it into an Array of characters just for the ease. The two pointers would be placed on the end of the string and would move towards each other.

Code

Complexity Analysis

Time = O(N) (Every element is visited once for comparison)

Space = O(N) (Because we are converting string into a char array.)

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github