String s of lowercase english letters

Assignment Help Basic Computer Science

Reference no: EM13160235

Magic strings, invented by the Bytelandians, are strings that contain immense magical power within themselves. Magic strings could bring luck and happiness to the Bytelandian citizens. Formally, a string S of length n is a magic string if it satisfies the following conditions:

All letters of S are lowercase letters of the English alphabet.
Si is lexicographically smaller than Sn-i+1 for all odd i from 1 to [n/2].
Si is lexicographically greater than Sn-i+1 for all even i from 1 to [n/2].

(Si (1 ? i ? n) denotes the ith character of S). For example, the word "difference" is a magic string, while "similar" is not.

Given a string S of lowercase English letters, write a program to find the longest magic string than can be obtained by removing some letters of S. If there are more than one solutions, choose the longest magic string which is lexicographically smallest.

The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case contains a string S written in a single line. S does not contain more than 2000 letters.

Reference no: EM13160235

Questions Cloud

Calculate number of unit sale in two different categories : Shopkeeper sale this good on breakeven. Calculate the no of Unit sale in two different categories This is a trading Company.

Common hazards in a healthcare facility : Describe at least five common hazards in a healthcare facility and describe how these hazards can be avoided or addressed in specific healthcare settings

Problem related to financing a new car : You Have saved $4000 for a down payment on a new car. the largest monthly payment you can afford is $350. the loan will have a 12% APR based on end of month payments. what is the most expensive car you can afford if you finance it for 48 months? 6..

How does it relate to national consumption : Why is it important, for an open economy, that investment not be consistently higher than saving? If this occurs how does it relate to national consumption, balance of trade and saving?

String s of lowercase english letters : Given a string S of lowercase English letters, write a program to find the longest magic string than can be obtained by removing some letters of S. If there are more than one solutions, choose the longest magic string which is lexicographically small..

State what is the value of the rate constant for reaction : What is the value of the rate constant (k) for this reaction? Points will be deducted if you do not include the correct sign and units of the rate constant. (b) Determine the half-life for this reaction in units of seconds

Which of lipid pairs is more susceptible tooxidation : Which of the following lipid pairs is more susceptible tooxidation?

Explain why the higher real wage would fail to increase : Assuming that factor markets are otherwise free and competitive, explain why the higher real wage would fail to increase the share of labor income in national income.

An algorithm that will sort a with a worst-case runtime : Let A be an array with n elements such that the first n -sqrt( n) elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that will sort A with a worst-case runtime substantially better than O(n logn).

User Account

All Pages