The task is to find out if a given string is comprised of multiple identical substrings. The first observation is that the substring cannot be longer than half of the length of the original string. The second observation is that the length of the total string has to be a multiple of the string that is tested, if it is not it can be discarded right away. Lastly, a string with the length of one can be discarded immediately.
A classic find the needle
in the haystack
problem. The task is to find if a string is contained within another string and return the index of the first position. If the string is not contained return -1
and if the needle
is empty, return 0
.
A subset of a list with the elements {a,b,c}
is {a,b}
. The task is to find all possible subsets. Sets in programming languages are usually not ordered. Therefore, the set {a,b,c}
is equivalent to {b,c,a}
.
The idea for the solution is a nested for
-loop that iterates over the results again and again, starting with one empty ([]
) result.
The goal of this task is to find all possible permutations of numbers in a list. For example, [1,2,3]
can become [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
. Mathematically, the number of possible permutations without using duplicates is n!
where n
is the number of unique elements in the list.
This problem can best be solved by using backtracing and recursion. The general idea is to put all possible digits in the beginning and then cut off the rest of the list and repeat the first step. Later, the list is assembled. The algorithm stops if there is only one item in the list because the only possible permutation is with itself. The other special case that needs to be handled is the empty list which must return the empty list itself.