# LeetCode 1768 - Merge Strings Alternately - Solution in Ruby

·

## Problem

LeetCode 1768 - Merge Strings Alternately

You are given two strings `word1` and `word2`. Merge the strings by adding letters in alternating order, starting with `word1`. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

## Solution steps

### Initialize the `merged` string

This line `merged = ""` initializes an empty string called `merged` to store the merged string.

`````` # @param {String} word1
# @param {String} word2
# @return {String}
def merge_alternately(word1, word2)
merged = ""

# To do

end
``````

The `merged` string is what our method is going to return. It's the result.

### Set up the loop

This line `for i in 0...[word1.size, word2.size].max` starts a loop that iterates over the indices from 0 to the maximum size of `word1` and `word2`.

The `...` range operator excludes the upper bound of the range.

``````# @param {String} word1
# @param {String} word2
# @return {String}
def merge_alternately(word1, word2)
merged = ""
for i in 0...[word1.size, word2.size].max
# To do
end
end
``````

### Compare word1 parameter

``````# @param {String} word1
# @param {String} word2
# @return {String}
def merge_alternately(word1, word2)
merged = ""
for i in 0...[word1.size, word2.size].max
merged += word1[i] if i < word1.size
end

end
``````

This line `merged += word1[i] if i < word1.size` appends the character at index `i,` of word1, to the merged string using the `+=` operator, if `i` is less than the size of word1.

We start with `word1` because this is a requirement of the challenge.

This ensures that characters are appended only when there are remaining characters in word1.

### Compare word2 parameter

Check if `i` is less than the size of word2.

If it is, append the character at index `i` of word2 to the merged string using the += operator.

``````# @param {String} word1
# @param {String} word2
# @return {String}
def merge_alternately(word1, word2)
merged = ""
for i in 0...[word1.size, word2.size].max
merged += word1[i] if i < word1.size
merged += word2[i] if i < word2.size
end

end
``````

### Return the `merged` string

We can get rid of the word `return`.

``````# @param {String} word1
# @param {String} word2
# @return {String}
def merge_alternately(word1, word2)
merged = ""
for i in 0...[word1.size, word2.size].max
merged += word1[i] if i < word1.size
merged += word2[i] if i < word2.size
end
merged
end
``````

## Solution

``````  # @param {String} word1
# @param {String} word2
# @return {String}
def merge_alternately(word1, word2)
merged = ""
for i in 0...[word1.size, word2.size].max
merged += word1[i] if i < word1.size
merged += word2[i] if i < word2.size
end
merged
end
``````

## Algorithm Efficiency

Algorithm efficiency is essential for achieving faster execution, scalability, optimal resource utilization, energy efficiency, scalable system design, and gaining a competitive advantage in specific domains.

My two favorite reasons to think about algorithm efficiency are resource utilization and scalability.

Resource utilization refers to the optimization of the use of system resources, such as CPU time, memory, disk space, or network bandwidth.

By minimizing resource consumption, efficient algorithms help maximize the utilization of available resources, leading to cost savings, improved system performance, and better overall system efficiency.

Regarding scalability, Efficient algorithms are designed to handle increasing input sizes without significant degradation in performance.

As the volume of data or the complexity of the problem grows, an efficient algorithm can still provide reasonable execution times.

This scalability is particularly important in scenarios where the input size may vary significantly or increase over time.

### Time complexity

The time complexity of this solution is O(max(N, M)), where N and M are the lengths of `word1` and `word2`, respectively.

This is because the loop iterates from 0 to the maximum size of `word1` and `word2`, which is determined by the larger length among the two strings.

The number of iterations is determined by the larger of the two sizes: `max(word1.size, word2.size)`.

Within each iteration, the operations performed (`merged += word1[i]` and `merged += word2[i]`) take constant time since accessing a character by index in a string is an O(1) operation.

As a result, the time complexity is directly proportional to the length of the longer string size, linear time complexity.

### Space complexity

The space complexity of your solution is O(N + M), where N and M are the lengths of `word1` and `word2`, respectively.

The reason is that we are creating a new string `merged` to store the merged string, which will have a length equal to the sum of the lengths of `word1` and `word2`.

Therefore, the space complexity is directly proportional to the combined lengths of the two input strings.

The space required by the `merged` string depends on the lengths of `word1` and `word2`, and in the worst case, it will be equal to the sum of their lengths: `word1.size + word2.size`.

In summary, this solution has a linear time complexity and linear space complexity in terms of the lengths of the input strings.

## Unit test

``````require_relative '../lib/contains_duplicate_217_leetcode'
require 'rspec'

describe ContainsDuplicate217Leetcode do

describe '#contains_duplicate' do
let(:klass) { ContainsDuplicate217Leetcode.new }

context 'when array contains duplicate' do
it 'returns true' do
numbers = [1,2,3,1]
expect(klass.contains_duplicate(numbers)).to be(true)
end
end

context 'when array does not contain duplicate' do
it 'returns false' do
numbers = [1, 2, 3, 4]
expect(klass.contains_duplicate(numbers)).to be(false)
end
end
end
end
``````

## Final thoughts

I hope this article helped you. Let me know if you have any questions. Your thoughts, suggestions and corrections are more than welcome.

By the way, feel free to drop your suggestions on new blog articles.

Hope to see you next time.