Minimum manipulations to type the string

Solution Approach

For using the operation copy & paste, we need to keep track of every substring that can be made from the string we've built so far (string S). In c++ we can use map, unordered_map or use hash or trie, anything else.

We'll perform copy & paste only if we can paste a string whose length is greater than 1. Cause, if it's length is 1, then it'll take same number of manupulation just to insert at the end.

Consider your first example. T=abcabab

Let's break it down.

At first, result string S is empty. So we've only one option here. Insert character 'a' at the end of S. Increase manipulations count by 1.

Now S = "a", remaining target string "bcabab", Saved substring:

Insert character 'b' at the end of S. Increase manipulations count by 1.

Now S = "ab", remaining target string "cabab", Saved substring: "ab"

Our substring list is not empty now. So we'll try to make substring from our >remaining target string and check if that exists in our substring list.

remaining target string "cabab", Saved substring: "ab"

So we'll first check if "ca" exists in our substring list. (not considering single character, cause we can just insert it) "ca" doesn't exist in the list, so we'll insert character 'c' at the end of S.

Increase manipulations count by 1.

Now S = "abc", remaining target string "abab", Saved substring: "ab", "bc, "abc"

remaining target string "abab", Saved substring: "ab", "bc, "abc"

first check if "ab" exists in our substring list. It does. Now check if "aba" exists. It does not.

So we'll save the string "ab" in a string variable (let's call it lastCopiedString), then insert "ab" at the end of S.

Increase manipulations count by 2.

Now S = "abcab", remaining target string "ab". Saved substring: "ab", "bc", "ca", "abc", "bca", "cab", "abca", "bcab", "abcab". lastCopiedString = "ab"

remaining target string "ab", Saved substring: "ab", "bc", "ca", "abc", "bca", "cab", "abca", "bcab", "abcab". lastCopiedString = "ab"

first check if "ab" exists in our substring list. It does. There's no letter left in target string. So check if the lastCopiedString is same as "ab". It's same in this case.

Increase manipulations count by 1.

Now S = "abcabab", remaining target string "".

Saved substring: "ab", "bc", "ca", "abc", "bca", "cab", "aba", "bab", "abca", "bcab", "caba", "abab", "abcab", "cabab", "bcabab", "abcaba", "abcabab" lastCopiedString = "ab"

We've our result , which is 6.

Your question is not clear here. From comment section, i understood you need to output the number of min manipulations require to change S to T . Also you haven't mentioned any constraints, max time complexity. Please try editing the post, and mention as much detail as you can. So that anyone sees your post, understands it.

I tried to share a generalized idea from what I've understood.

We can have an O(n^2 * log n) dynamic program state of dp[i][sub] where i is the current index and sub is which substring was used to create the suffix of the prefix ending at the ith index.

dp_0 = 1 // A constant

dp[i][sub] = min(
  // Insert one character
  1 + dp[i-1][best], // best is the min for dp[i-1]
  
  // Only pasting 
  1 + dp[j-1][sub]
    if exists sub T[j..i] in dp[j-1]
    
  // Copy and paste
  2 + dp[j-1][best]
    if we've seen T[j..i] before j;
    which we can check in log n time
    by storing an ordered list of
    indexes where each substring
    we've seen appears, hashed by
    the substring.
)

for j from i-1 down to 1

Python code:

import bisect

# Assumes the string does
# not contain the substring,
# "best" :)
def f(T):
  seen = {}
  dp = [{"best": float('inf')} for _ in range(len(T) + 1)]
  dp[0]["best"] = 1

  for i in range(1, len(T)):
    sub = T[i]

    # Insert one character
    dp[i]["best"] = min(dp[i]["best"], 1 + dp[i-1]["best"])

    for j in range(i-1, 0, -1):
      sub = T[j] + sub

      if sub in seen:
        seen[sub].append(i)
      else:
        seen[sub] = [i]

      # Copy and paste
      end_of_sub_in_T_before_j = float('inf')

      insertion_pt = bisect.bisect_left(seen[sub], j)
      if insertion_pt - 1 >= 0:
        end_of_sub_in_T_before_j = seen[sub][insertion_pt - 1]

      if end_of_sub_in_T_before_j < j:
        dp[i][sub] = 2 + dp[j-1]["best"]

      # Paste only
      if sub in dp[j-1]:
        dp[i][sub] = min(dp[i][sub], 1 + dp[j-1][sub])

      # Best for dp[i]
      dp[i]["best"] = min(dp[i]["best"], dp[i][sub] if sub in dp[i] else float('inf'))
    
    seen[T[0] + sub] = [i]

  return dp[len(T)-1]["best"]

strs = [
  "abcabab",
  "aaaaaaaaaaa"
]

for T in strs:
  print(T)
  print(f(T))
  print("")