Aang's Training Sequence - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25 mins
  • 🛠️ Topics: String Manipulation, Dynamic Programming

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the goal of the problem?
    • The goal is to find the maximum k-repeating value for a given move in a sequence.
  • How do we define k-repeating?
    • A substring is k-repeating if it consists of the technique move repeated k times consecutively.
HAPPY CASE
Input: 
    sequence = ""airairwater""
    move = ""air""
Output: 
    2
Explanation:
    ""airair"" is a substring that repeats ""air"" twice in the sequence.

EDGE CASE
Input: 
    sequence = ""waterfire""
    move = ""air""
Output: 
    0
Explanation:
    ""air"" does not appear in the sequence, so its k-repeating value is 0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For k-repeating problems, we want to consider the following approaches:

  • String Manipulation: We can check for repeating patterns by constructing a string move * k and checking if it is a substring of sequence.
  • Dynamic Programming: While not necessary in this case, DP can be used to optimize searching through the sequence for larger values of k.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will incrementally check how many times the string move repeats in the sequence by checking if move * k is a substring of sequence. We continue until we find the largest k such that move * k is a valid substring.

Steps:

  1. Initialize k to 0: Start by assuming k = 0 and increment k as long as move * (k + 1) is a substring of sequence.

  2. Check for Substring:

    • Use the in operator to check if move * (k + 1) exists in the sequence.

  3. Return k:

    • Once move * (k + 1) is no longer a substring, return k as the maximum k-repeating value.

4: I-mplement

Implement the code to solve the algorithm.

def max_k_repeating(sequence, move):
    k = 0
    
    # Keep increasing k while move * k is a valid substring in sequence
    while (move * (k + 1)) in sequence:
        k += 1
    
    return k

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: sequence = ""airairwater"" move = ""air""
  • Expected Output: 2

Example 2:

  • Input: sequence = ""fireearthfire"" move = ""fire""
  • Expected Output: 1

Example 3:

  • Input: sequence = ""waterfire"" move = ""air""
  • Expected Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the length of sequence and m is the length of move.

  • Time Complexity: O(n * m) because we construct the string move * k and check if it is a substring of sequence for increasing values of k.
  • Space Complexity: O(k * m) to store the repeated string move * k while checking for each repetition.