Longest Palindrome length in sub-array with rearrange


Problem statement:

Find the longest even palindrome length of the sub array from the given string of digits. The palindrome can be formed by rearranging the characters as well.

Example:
Given a string "1234535498"
The palindrome formed can be 345543 and the length is 6.

My Solution:
Create a boolean array which will be true if it can form a palindrome. Find the contiguous boolean subarray with maximum number of true values. If the length is odd rerun the same with the subarray.

Comments are welcome to provide a better solution or evaluate this solution.


Algorithm:
  1. Iterate through the input string character by character.
  2. For each character, have a counter and increment it for each loop.
  3. Check if the character is present in the character array and get the last index of it.
  4. if the last index is not of -1, insert true in the boolean array for the last index and the counter.
  5. finally insert the character to the character array for the counter.
  6. After the above steps, we will get the boolean array filled with true for elements which can form palindrome.
  7. The next step is to find the longest contiguous boolean sub-array in the boolean array.

Step by Step explanation:
  1. Create a boolean array of same length as of the input string. 
  2. Read each character in the string one by one.
    1. 1234535498 - input string
  3. Create two new arrays of the length same as input string, first one is character array and the second one is boolean array.
    1. input 1 234535498 - counter 0
    2. index of 1 in character [] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,false,false,false,false,false,false,false,false]
    5. insert 1 in the character array.
    6. character[] - [1, null,null,null,null,null,null,null,null,null]
    1. input 1 2 34535498 - counter 1
    2. index of 2 in character [1, null,null,null,null,null,null,null,null,null] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,false,false,false,false,false,false,false,false]
    5. insert 2 in the character array.
    6. character[] - [1, 2,null,null,null,null,null,null,null,null]
    1. input 12 3 4535498 - counter 2
    2. index of 3 in character [1, 2,null,null,null,null,null,null,null,null] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,false,false,false,false,false,false,false,false]
    5. insert 3 in the character array.
    6. character[] - [1, 2,3,null,null,null,null,null,null,null]
    1. input 123 4 535498 - counter 3
    2. index of 4 in character [1, 2,3,null,null,null,null,null,null,null] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,false,false,false,false,false,false,false,false]
    5. insert 4 in the character array.
    6. character[] - [1, 2,3,4,null,null,null,null,null,null]
    1. input 1234 5 35498 - counter 4
    2. index of 5 in character [1, 2,3,4,null,null,null,null,null,null] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,false,false,false,false,false,false,false,false]
    5. insert 5 in the character array.
    6. character[] - [1, 2,3,4,5,null,null,null,null,null]
    1. input 12345 3 5498 - counter 5
    2. index of 3 in character [1, 2,3,4,5,null,null,null,null,null] is 2.
    3. Make the 2nd (index) element and 5th (counter) element as true.
    4. boolean[] - [false, false,true,false,false,true,false,false,false,false]
    5. insert 3 in the character array.
    6. character[] - [1, 2,3,4,5,3,null,null,null,null]
    1. input 123453 5 498  - counter 6
    2. index of 5 in character [1, 2,3,4,5,3,null,null,null,null] is 4.
    3. Make the 4th (index) element and 6th (counter) element as true.
    4. boolean[] - [false, false,true,false,true,true,true,false,false,false]
    5. insert 5 in the character array.
    6. character[] - [1, 2,3,4,5,3,5,null,null,null]
    1. input 1234535 4 98  - counter 7
    2. index of 4 in character [1, 2,3,4,5,3,5,null,null,null] is 3.
    3. Make the 3rd (index) element and 7th (counter) element as true.
    4. boolean[] - [false, false,true,true,true,true,true,true,false,false]
    5. insert 4 in the character array.
    6. character[] - [1, 2,3,4,5,3,5,4,null,null]
    1. input 12345354 9 8  - counter 8
    2. index of 9 in character [1, 2,3,4,5,3,5,4,null,null] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,true,true,true,true,true,true,false,false]
    5. insert 9 in the character array.
    6. character[] - [1, 2,3,4,5,3,5,4,9,null]
    1. input 123453549 8  - counter 9
    2. index of 8 in character [1, 2,3,4,5,3,5,4,9,null] is -1.
    3. Skip updating boolean array as index is -1.
    4. boolean[] - [false, false,true,true,true,true,true,true,false,false]
    5. insert 8 in the character array.
    6. character[] - [1, 2,3,4,5,3,5,4,9,8]
Now find the longest contiguous boolean sub array in the boolean array. In our case it is 6. 2nd to 7th element in the boolean array.



Location: India

Comments

Post a Comment

Popular posts from this blog

How to modify buttonDataSetup for RPM Euro Gamepad to work in Fifa 18 on Windows

Image
        STEP 1      Identify the RPM Euro Gamepad/Joystick name connected to your Windows Connect your Gamepad to PC Press Windows Key and search for "Game Controllers" Select "Set up USB Game Controllers" from the search list. This will display the device name connected. Copy the name from the list. In my case it is below Update buttonDataSetup.ini Goto Documents and open Fifa folder Edit the buttonDataSetup.ini file Search for the gamepad name which obtained in the first step in the file If present modify it or else add the below to the end of the file. Controller_054 is just a unique name, you can add anything AddAlias is what important. Feel free to modify the mappings according to your needs. AddController "Controller_054" AddAlias "Controller (XBOX 360 For Windows)" AddMap XENON_LEFT_ANALOG_STICK_RIGHT VB_AI_LS_RIGHT AddMap XENON_LEFT_ANALOG_STICK_UP VB_AI_LS_UP AddMap XENON_LEFT_ANALOG_STICK_LEFT VB_AI_LS_LEFT AddMap XENON_LEFT_A...
Read more

How to compile and run using javac and java command in java11 or later

Image
In this blog we will see how to compile and run java class in command line using jdk11 . From java9 , modules are introduced in java ecosystem and with that there is a change in the command args to compile or run our class code if we intend to use modules. Please note we can also stick to the old classpath way. The sample project is available in github and the link to the same is provided at the end. It comprises of one module and an external lib folder. The project is very simple, which tells the passed text is a number or not. First we create a module and a class and then add a jar which is needed by the module. The directory structure looks like below Compile: Now to compile the Main.java, go to the project location(sampleJava folder) and run the below command. C:\Users\surat\git\repository\examples\sampleJava >  javac --module-source-path src\modules --module-path lib -d target src\modules\testModule\com\Main.java If you look into the structure we now create a modules dire...
Read more