Array / String

An array is a fundamental data structure in programming that consists of a collection of elements, each identified by at least one array index or key. Arrays are used to store data elements of the same type. They are particularly useful for storing and manipulating ordered data efficiently.

When are Arrays (Lists) Used?

Arrays are used in a variety of situations where a collection of elements needs to be stored such that they can be efficiently accessed, manipulated, and traversed.

Here are some common scenarios where arrays are particularly useful:

• Storing data: Arrays provide a way to store multiple items, such as a list of numbers, user information, etc., under a single variable.
• Accessing elements: Arrays allow for rapid access to any element via its index, making it easy to retrieve or update elements.
• Iterative operations: When operations need to be performed on a sequence of items, arrays can be looped through using indices or iterators.
• Sorting and searching: Arrays are fundamental in algorithms for sorting (e.g., merge sort, quicksort) and for efficient searching (e.g., binary search).

Recognizing Array Problems

• Array problems often involve manipulation or querying of a sequence of elements. You can identify that a problem might require using an array when:
• The problem mentions operations on a collection of items that are ordered or unordered.
• You need to find, replace, or remove elements based on certain conditions.
• The problem involves sorting or rearranging elements based on specific criteria.
• You are asked to track frequencies or counts of unique items.

Top Patterns for Solving Array Problems

1. Two-Pointer Technique Description: This technique uses two pointers to traverse the array, typically from opposite ends or from the same starting point, to efficiently solve problems without needing extra space. Common Use: Used in problems like reversing an array, finding a pair that sums to a target value, or merging two sorted arrays.
2. Sliding Window Description: This involves creating a 'window' over a portion of the array which can expand or contract as needed. It's useful for finding a subset of the array that satisfies certain conditions. Common Use: Finding the longest substring without repeating characters, computing the maximum sum of a subarray of a fixed size.
3. Hashing (Using Hash Maps) Description: Hash maps are incredibly useful for tracking the occurrences of elements in an array, allowing for quick lookups, insertions, and deletions. Common Use: Checking for duplicates, counting the frequency of items, or finding the first unique element.
4. Sorting Description: Sorting can simplify many problems by bringing order and making it easier to process data. Common Use: Finding missing or additional elements, checking for the presence of a specific sequence, or simplifying the merging of intervals.
5. Dynamic Programming Description: This method solves problems by breaking them into smaller subproblems and storing the results of these subproblems to avoid computing the same results multiple times. Common Use: Solving optimization problems such as the maximum sum subarray or the number of ways to sum to a target.

1768. Merge Strings Alternately / Easy

https://leetcode.com/problems/merge-strings-alternately/description/

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.

 
Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r
Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s
Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d
 

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

Explanation

In most cases, LeetCode Easy problems have a straightforward solution that can be derived from the description or the examples provided.

Strings can be represented in several ways, each suited for different kinds of operations:

List of Characters: A string can be split into a list of its characters, allowing for easy iteration and modification. This is useful for problems where you need to manipulate individual characters or their order, also with help of indexes.

Tree Structures: For complex string operations, like searching for substrings or sorting operations, Python can use advanced data structures like trie trees or suffix trees (we will cover later).

Think of Strings as Lists: In Python, you can think of strings almost like lists of letters. This makes it easier to pick out each letter one by one.

Merge by Alternating Letters: You'll take one letter from the first string, then one from the second string, and keep alternating like this. You add each of these letters to a new list because lists in Python can change size easily, unlike strings.

When the Strings are Different Lengths?: If one string runs out of letters because it's shorter, you just continue adding the remaining letters from the longer string to the list.

Turn the List Back into a String: Once all letters are in the list in the right order, you change this list back into a string.

def mergeAlternately(word1, word2):
    res = []
    i = 0
    while i < len(word1) and i < len(word2):
        res.append(word1[i])
        res.append(word2[i])
        i += 1

    res.append(word1[i:])  # Append remaining characters from word1
    res.append(word2[i:])  # and word2
    return "".join(res)

word1 = "ab"
word2 = "pqrs"

mergeAlternately(word1, word2)

'apbqrs'