SDE - 2

We can use two pointers, i and j, where i is the slow runner and j is the fast runner.

We can solve the problem by iterating through the numbers from 1 to n and using linear search to determine whether each number is in the array. The first number we cannot find is the smallest missing integer. This approach results in quadratic time complexity.

Define a function called recurse that takes in two integer values, i and j, where i represents the current character to be processed in the string S and j represents the current character in the string T.
Initialize a dictionary called memo to cache the results of our different recursive calls.
Check the base cases:

If either string is finished, return 0 or 1 depending on whether the entire string T has been processed successfully.

Another base case to consider is if the remaining length of string S is less than that of string T; in this case, a match is impossible, so prune the recursion and return 0.

Next, check if the current pair of indices (i, j) exists in the dictionary. If it does, return the cached value.

If not, proceed with normal processing by comparing the characters S[i] and T[j].
Store the result of recurse(i + 1, j) in a variable; as explained above, this result is needed regardless of whether the characters match.
If the characters match, add the result of recurse(i + 1, j + 1) to this variable.

Finally, store this variable’s value in the dictionary with the key (i, j) and return it as the answer.

Count the number of occurrences of each word using a hashmap
(Can use a Counter in Python).

Initialize answer=0, central=false. The answer will denote
The number of words in the final string and
The boolean variable central will denote whether we have a central word.

For each palindromic word, do the following. If count[word] is even,
increasethe  answer by count[word]. Otherwise, if count[word] is odd,
increase answer by count[word]−1 and set central=true (we can use the
word as a central word).

For each non-palindrome word such that word[0] (we need this condition to consider each pair only once and not twice,
e.g. we don't want to consider both ba and ab separately)
increase answer by 2⋅min(count[word],count[reversedWord])
(we use min(count[word],count[reversedWord]) pairs of the corresponding words).

If central=true, increase answer by 1.

Return 2⋅answer. (Because each word has a length of 2).