0 like 0 dislike
1,636 views
| 1,636 views

0 like 0 dislike

QUESTION 1 :
We are given a string text of length N consisting of the letters 'a', 'b' or 'c'. We can insert any of those letters before or after any letter in the string.
The goal is to insert letters into text so that it will follow the pattern "abcabca..."; i.e. it should start with a letter 'a', letter 'a' should be followed by 'b', letter 'b' should be followed by 'c', and letter 'c' by 'a'. The string may end with any of those three letters.

What is the minimum number of letters we need to insert into text?

Write a function:

int solution(String text);

that, given a string text of length N, returns the minimum number of insertions needed to make text follow the described pattern.

Examples:

For text = "aabcc" we need to insert letters 'b' and 'c' between the pair of letters 'a', and then insert letters 'a' and 'b' between the two letters 'c'. This way we obtain the string "abcabcabc" and the function should return 4.
For text = "abcabcabca", we do not need to insert any letters. The string already follows the required pattern, so the function should return 0. Note that text does not need to end with letter 'c'.
For text = "bcaaa", letter 'a' should be inserted at the beginning of text, and then letters 'b' and 'c' should be inserted between the two pairs of letters 'a'. This way we obtain the string "abcabcabca" and the function should return 5.
Assume that:

N is an integer within the range [1..100];
string text consists only of the following characters: "a", "b" and/or "c".

QUESTION2:
You are given an array segments consisting of N integers denoting the lengths of several segments. Your task is to find among them four segments from which a rectangle can be constructed. What is the minimum absolute difference between the side lengths of the constructed rectangle?

Write a function:

int solution(int[] segments);

that, given an array segments, returns the minimum absolute difference between the side lengths of the constructed rectangle or −1 if no rectangle can be constructed.

Examples:

For segments = [2, 2, 2, 2, 2], we can construct only a 2 x 2 rectangle out of the given segments. The function should return 0.
For segments = [911, 1, 3, 1000, 1000, 2, 2, 999, 1000, 911], we can construct three rectangles: 2 x 911, 2 x 1000, and 911 x 1000. Out of those three possibilities, the best one is 911 x 1000. The function should return 89.
For segments = [4, 1, 1, 1, 3], we cannot construct any rectangle out of the given segments. The function should return −1.
For segments = [1, 1, 1], we cannot construct any rectangle out of the given segments. The function should return −1.
Assume that:

N is an integer within the range [1..30];
each element of array segments is an integer within the range [1..1,000].

by Expert (111,330 points)