---

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

---

Github Repository

In case you want to follow along, click here.

---

Celebrate

---

Let's become friends

• Github

• LinkedIn

• Hashnode

• Youtube

---

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.

---