HI all,

I recently attempted HackerRank test for Indium. Following are the questions.

1. Given a string str , and the allowed operation is replace any character with any other character.
   You have to make the string str as palindrome with minimum number of operations and return the string str which is lexicographically ordered by rearranging the characters in the string str.

   Example:
   Input: str= "bacde"
   Output: "abcba"

   Explanation:
   Stage 1: With minimum number of operations, make the string palindrome
   str= "bacde", here replace the characters 'd' with 'a' and 'e' with 'b'
   Now, the str ="bacab" become palindrome with 2 operations which is least we can do.
   Stage 2 : Return the lexicographically ordered palindromic string
   We have to rearrange the previous step result to make it lexicographally ordered.
   i.e., rearrange it like this, bacab ---> abcba
   return str= abcba

2. (Variation of problem 1) Given a string str , and the allowed operation is replace any character with any other character.
   With minimum number of operations and rearranging the characters(i.e., replacment and rearrangment of characters), make the string Palindrome and return the string str which is lexicographically ordered

   Example:
   Input: str= "bacbe"
   Output: "abcba"

   Explanation:
   Stage 1: With minimum number of operations, make the string palindrome
   str= "bacbe", here replace the characters 'e' with 'a', with 1 operation
   Now, the str can be palindromic by rearranging characters "abcba" or "bacab" become palindrome with 1 operation which is least we can do.
   Stage 2 : Return the lexicographically ordered palindromic string
   We have to rearrange the previous step result to make it lexicographally ordered.
   i.e., rearrange it like this, bacba ---> abcba
   return str= abcba

   NOTE: Differennce between Problem 1 and 2 is,in Problem 1, After replacemnt we need to make it palindrome and post that we need to return lexicographically smaller palindrome, whereas in Problem 2, After both replacement and rearrangement, we need to make the string palindrome and return lexicographically smaller palindrome

3. Given an array arr with n elements where n>=3, find the minimum sum of three elements arr[i], arr[j], arr[j] chosen from the array arr, given that it should satisfy below condition
   i < j < k and arr[i] < arr[j] > arr[k], i.e., first element should be lesser than second element and second element should be greater than third element.
   Example:
   Input: arr = [1,2,3,2,3,1]
   Output: 4

   Explanation:
   i =0, j= 1 or 3, k=5, which gives the minimum sum of 4 (1 + 2 + 1) and also satisfies the given condition
   i.e.,arr[0]< arr[1] > arr[5] and i < j < k

My solution didn't pass all test cases for both problems.
Problem 1: I went with naive approach with help of frequency array, but didn't pass 5/20 cases
Problem 2: I solved with recursion, but faced Time Limit Exceeded (TLE) error, as we need to implement DP, not sure whether we need to do 2D or 3D DP

I would like to know how we can solve this 2 problems.
If you could solve it, kinldy share it. It will be very much helpful.

Thanks.