Tag Archives: codechef

Check if a string is a double string

Given a string, we need to check if a string is a double string possibly by deleting a character.

A double string is a repetition of two strings affixed together.
For example the following strings are double strings
"aa", "meme", "abbabb"
Where as the follwing are not double strings
"ab", "abc", "acbab"

However "acbab" can be be a double string if we remove "c" from it.

This problem was appeared in Codechef March 2016 long contest. Here is the link.

Let us try to analyze the problem. Consider the base case first. A string of length 0 or 1 can never be a double string. Hence, we have to consider the strings of length > 1. Also we can observe that a double string is always of even length.

Case 1:
If the given string is of even length, we simply need to check if it is a double string by checking if the left half and right half are equal.
No need to consider the case of deleting a character because, if we delete a character, it’s length will be odd which will never be a double string.

Case 2:
If the string is of odd length, we have to delete a character before checking if it is a double string. How to find out which character to be deleted?

Consider the following cases
"cabab", delete first character
"acbab", delete second character
"abcab", delete third character
"abacb", delete fourth character
"ababc", delete fifth character

So it appears that we should try to remove each possible character and check if it is a double string. However since we want to check for a double string,
the left and right half should atleast be similar if not equal.

Consider an example “acbab”, we can divide the string into longer and shorter halves in two ways
("acb", "ab")
("ac", "bab")

Since the first pair of string differ by only character (In other words, their edit distance is just 1)

So we just need to check if the edit distance between the longer and shorter strings is at most 1.

Here is the C++ implementation of the above algorithm. It runs in O(n) time.

Decreasing string

Given a number K, Find the shortest and smallest string  which has K positions in it, such that the character at that position is alphabetically greater than the character immediately after it. Only the lower case alphabets [a-z] are allowed.

For example consider K = 1

“ba” is the shortest and smallest string possible. There are other possibilities like “ca”, “bad”. But “ca” cannot be the answer because “ba” is alphabetically smaller than “ca”. Similarly “bad” cannot be the answer because it’s length is greater than “ba”.

This problem is from Codechef. If you want to solve it, follow the problem link.

Here is how we can solve the problem. Let us look at some of the answers.

K = 1, “ba”

K = 2, “cba”

K = 3, “dcba”…

If you observe the pattern, this is simply reverse order of alphabets. We can happily reverse the alphabets if K < 26. What happens if K = 26? The pattern repeats, and the repeating pattern should be added in the beginning.

So for K = 26, the answer is “bazyxwvutsrqponmlkjihgfedcba”.

Here is the Python implementation of this algorithm.

Up down array

Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]

For example consider the array A =[6, 9, 36, 24, 42]

The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We have to find out one such answer.

We can solve this problem in a simpler way by sorting the array first. Considering the same example as above

Sorted(A) = [6, 9, 24, 36, 42]

Method1: Start from the second element and swap the elements in pairs

6, 9<-> 24, 36<-> 42 ===>  6, 24, 9, 42, 36

Method2: Interleave the elements of the second half into the first half in reverse order

It becomes 6, 42, 9, 36, 24