Growing String

Approach:

• Recognize that Bob's string on day 'D' is the initial string 'S' repeated 'D' times.
• We want to find the minimum day 'D' such that 'T' is a subsequence of 'S' repeated 'D' times.
• We can use dynamic programming to find the earliest point in Bob's growing string where each prefix of 'T' can be formed as a subsequence.
• Let 'dp[j]' be a pair representing the earliest day and the index within that day's copy of 'S' where the prefix 'T[0...j]' can be formed as a subsequence, ending with the character 'T[j]' at that specific index in that specific copy.
• Since the structure of each appended 'S' is the same, we can optimize by only storing the index within a single copy of 'S' and the day number.
• To efficiently find the next occurrence of a character in 'S' from a given starting index, precompute the indices of the next occurrences of each character.

Algorithm:

• Initialize 'N' = length of 'S', 'M' = length of 'T'.
• Create a 2D array 'next_occ' of size 26 x (N + 1). This will store the index of the first occurrence of a character in 'S' at or after a given index. Initialize all values to -1.
  • Iterate 'c' from 0 to 25 (for 'a' to 'z'):
    • Set 'next_occ[c][N]' to -1.
    • Iterate 'i' from N - 1 down to 0:
      • Set 'next_occ[c][i]' to 'next_occ[c][i + 1]'.
      • If S[i] == ('a' + c), set 'next_occ[c][i]' to 'i'.
• Create a DP array 'dp' of size 'M', storing pairs of integers (day, index_in_S). Initialize all pairs with a value representing infinity (e.g., a day value greater than M, and an index value greater than or equal to N). Let's use (M + 1, N) for infinity.
• Handle the base case for 'T[0]':
  • Find the first occurrence of 'T[0]' in 'S' using 'next_occ[T[0] - 'a'][0]'.
  • If the index 'first_idx' is not -1:
    • Set dp[0] = (1, first_idx).
  • Else (T[0] is not present in S):
    • Return -1 (as T cannot be formed).
• Iterate 'j' from 1 to M - 1 (to calculate dp for prefixes T[0...j]):
  • Let 'prev_day' = dp[j-1].first, 'prev_idx' = dp[j-1].second.
  • If 'prev_day' is infinity (M + 1), continue (T[0...j-1] cannot be formed, so T[0...j] also cannot).
  • Find the next occurrence of 'T[j]' in 'S' starting from index 'prev_idx + 1' using 'next_occ[T[j] - 'a'][prev_idx + 1]'.
  • Let 'curr_idx' be the result of the lookup.
  • If 'curr_idx' is not -1:
    • 'T[j]' is found in the same copy of 'S' after the position where 'T[0...j-1]' ended.
    • Set dp[j] = (prev_day, curr_idx).
  • Else ('curr_idx' is -1, 'T[j]' is not found in the rest of the current copy of 'S'):
    • We need to move to the next copy of 'S'. Find the first occurrence of 'T[j]' in 'S' starting from index 0 using 'next_occ[T[j] - 'a'][0]'.
    • Let 'curr_idx_from_start' be the result of the lookup.
    • If 'curr_idx_from_start' is not -1:
      • 'T[j]' is found as the first occurrence in the next copy of 'S'.
      • Set dp[j] = (prev_day + 1, curr_idx_from_start).
    • Else ('curr_idx_from_start' is -1, 'T[j]' is not present in S at all):
      • It's impossible to form 'T'. Set dp[j] to the infinity value (M + 1, N) and continue.
• After the loop, the earliest day to form 'T' is stored in dp[M-1].first.
• If dp[M-1].first is the infinity value (M + 1), return -1.
• Else, return dp[M-1].first.

O(N + M).

The precomputation of the 'next_occ' table takes O(N * 26), which simplifies to O(N) because 26 is a constant. The dynamic programming loop iterates M times. Inside the loop, operations like array lookups and assignments are O(1). Thus, the DP part takes O(M) time. The overall time complexity is dominated by these two parts, resulting in O(N + M).

O(N + M).

The 'next_occ' table requires O(N * 26) space, which simplifies to O(N). The DP table 'dp' requires O(M) space to store M pairs. Thus, the overall space complexity is of the order O(N + M).