Algorithm: Longest Continuous Palindrome in a String

Anuj Kumar Jha — Sat, 20 Apr 2019 16:21:38 +0000

Prerequisite: Basic programming experience in any language
Problem: Given a string find the longest continuous palindrome in it. We should not change position of any character, instead we should find how many palindromes are there and which is longest among them. For ex: if given input string is "madam" then possible palindromes are ("m", "a", "d", "a", "m", "ada", "madam") output would be "madam" as its longest palindrome. Or if given input is "Crore" output would be "ror"
If you still have confusion in understanding the problem, refer below link
https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
For this problem we can assume given input contains all lower case character only.
I will write code in Java, But you can apply this logic to any language of your choice.
Approach 1- Brute Force:
A brute force solution would be to consider/generate all substring and check if they are palindrome and find the largest among the string which are palindrome. This algorithm will run in O(n³) considering n is length of the string.
Approach 2:
We can reduce the time complexity to O(n²) by following below method.
To solve this problem we can try to find largest palindrome from each index. For each index we will keep two pointer start and end. start index will represent left side and end index will be right side. We will check if character at both index is same then we will move start to further left and end to further right. We keep doing it until the character at left and right index are not same. Finally our substring would be palindrome. This result we will compare with the length of previous result and if its greater we will update the result. Below is the complete code for this

public static String longestPalindrome(String str) {
    if (str == null || str.length() <= 1) return str;
    String res = str.substring(0,1);
    for (int i = 0; i < str.length(); i++) {
        String str1 = expands(str, i, i);

        String str2 = expands(str, i, i + 1);
        if(str1.length()>res.length()){
            res = str1;
        }
        if(str2.length()>res.length()){
            res = str2;
        }

    }

    return res;
}


private static String expands(String str, int start, int end) {
    while(start>=0&& end<str.length() &&  str.charAt(start)==str.charAt(end)){
        start--;
        end++;
    }
    return  str.substring(start+1, end);
}

This algorithm run has time complexity of O(n²).
Approach 3:
If you see previous problem we are creating many substring which is memory wastage.We can still improve our algorithm to avoid creating substring each time and instead return length from expand method. And based on length we can have our start and end index which can be used to extract final subString. Below is the code to do this.

public static String longestPalindromic(String str) {
    if (str == null || str.length() <= 1) return str;
    int start = 0;
    int end = 0;
    for (int i = 0; i < str.length(); i++) {
        int len1 = expand(str, i, i);
        int len2 = expand(str, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return str.substring(start, end + 1);
}


private static int expand(String str, int start, int end) {
    while (start >= 0 && end < str.length() && str.charAt(start) ==     str.charAt(end)) {
        start--;
        end++;
    }
    return end - start - 1;
}

Thank you for reading. Do comment if any bug found.
You can follow me on Twitter and GitHub

Understanding Handler, Looper and Handler Thread

Anuj Kumar Jha — Sat, 16 Feb 2019 06:14:52 +0000

In my first ever article I am going to try to simplify the Handler, Looper and Handler thread class and the relation between them. Till now I have been struggling to understand the relation between them. So I thought of simplifying this for other people like me.

Let’s get started.

First of all lets see what is Handler Thread: Handler thread is nothing but a simple thread(as in Java) which execute certain task. It eventually extends the Thread class and also implement the run method of it. And to start it we can do Thread.start() method as with all others threads in Java.

So what is the difference?

So Imagine that you run into a problem where you want your thread to be running and you being able to post/send task to it so that it executes them basically what I mean is you want to reuse your thread. The way to do this in Java is

Keep a thread alive i.e. do not let it come out of run method.
Maintain a queue and post your task in it.
Process the queue in your run method ie execute task one by one or when it comes
Finish/Terminate the thread once done
I guess you see the issue that you have to manage lots of things and if not lot then at-least you should be very careful with this approach. But the good thing about Handler thread is it you can avoid all these. It comes with a message queue associated which can be used to send any message/task to this thread once it’s started. So how does Handler Thread does it?

Android has 3 main components to handle these which is used by HandlerThread. Let’s go through them once.

Looper: Looper is a worker that keep a thread alive, It loops over message queue and send the message to respective Handler.

Handler: This class is responsible for enqueuing any task to message queue and processing them. Each Handler can be associated with one single thread and that thread’s message queue.

Message Queue: This class holds the list of messages to be dispatched by the looper. You can just call Looper.myqueue() to get list of messages. We do not normally deal with it.

Of-course you can use above three components with normal thread class also. You can create your own thread and use all above mentioned components. The process to do this is mentioned below

Create a Thread class
Call Looper.prepare inside run method.
instantiate your Handler class and implement handleMessage method.
Call Looper.loop()
I can write the code to do this but since I do not want you to follow that approach I will skip that. As this is not very efficient way, so Android has made job simpler by introducing HandlerThread.

We can write our own class which extends HandlerThread.. Each HandlerThread class has a looper associated with. We can use this looper to create Handler and then we can start enqueuing/sending message to this thread.

Steps to do it.

Create a class that extend HandlerThread
Instantiate your handlerThread class
call start method // your thread is running now
Create/Instantiate your Handler by using looper from handler thread created above

public abstract class BaseHandlerThread extends HandlerThread
{
public BaseHandlerThread(String name)
{
super(name);
}
@override
protected void onLooperPrepared()
{
initHandler();

}
private void initHandler()
{
mHandler = new Handler(getLooper()) {
@override
public void handleMessage(Message msg)
{
//
}
};
}
}
We can simply create instance of BaseHandlerThread and then call start() method on it. Once start is called Looper gets prepared. After Looper is prepared we get a callback where we are initialising the Handler. A handler can only be initialised after looper os prepared. Now you can use this handler to enqueue message.
When you want to terminate this thread just call quitSafely() method on your handler thread instance or quit() for OS version older then JELLY_BEAN_MR2.

When you do not want to create separate class and still want to use HandlerThread you can follow below step. Note that When you create a new Handler, it is bound to the thread / message queue of the thread that is creating it. So be very sure about how you are creating the Handler.

//Create Handler
mHandlerThread = new HandlerThread("name");
mHandlerThread.start();
mHandler = new Handler(mHandlerThread.getLooper());
Thats about it. Feel free to share your input and point to improve on.

DEV Community: Anuj Kumar Jha

Algorithm: Longest Continuous Palindrome in a String

Understanding Handler, Looper and Handler Thread