Funny String Java Solution

Question

I'm a little rusty in Java, but I'm using it to get ready for interviews. Here's the problem description from HackerRank:

Problem Statement

Suppose you have a string \$S\$ which has length \$N\$ and is indexed from \$0\$ to \$N−1\$. String \$R\$ is the reverse of the string \$S\$. The string \$S\$ is funny if the condition \$|S_i−S_{i−1}|=|R_i−R_{i−1}|\$ is true for every \$i\$ from 1 to \$N−1\$.

(Note: Given a string str, stri denotes the ascii value of the ith character (0-indexed) of str. |x| denotes the absolute value of an integer x)

Input Format

First line of the input will contain an integer T. T testcases follow. Each of the next T lines contains one string S.

Constraints

• \$1 \le T \le 10\$
• \$2 \le\$ length of S \$\le 10000\$

Output Format

For each string, print Funny or Not Funny in separate lines.

This passing solution took me about 20 minutes, so that might be a bit long given the difficulty of the problem. I'm open to critiques on my speed too.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    private static boolean isFunny (String s)
    {
        String rev = reverse(s);
        boolean stillEq = true;
        for (int i = 2; i < s.length() && stillEq; ++i)
        {
            int comp = (int)s.charAt(i) - (int)s.charAt(i-1);
            int comp2 = (int)rev.charAt(i) - (int)rev.charAt(i-1);
            stillEq = Math.abs(comp) == Math.abs(comp2);
        }

        if (stillEq)
            return true;
        else
            return false;
    }

    private static String reverse (String s)
    {
        if (s.length() > 0)
            return s.charAt(s.length()-1) + reverse(s.substring(0, s.length()-1));
        else
            return "";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tests = sc.nextInt();
        for (int i = 0; i < tests; ++i)
        {
            String out = isFunny(sc.next()) ? "Funny" : "Not Funny";
            System.out.println( out );
        }
    }

Answer 1

• Bug

  The main loop starts at i = 2. That is, s.charAt(1) - s.charAt(0) is never attended to. Suspicious, isn't it?

• Naming

  A name comp (and comp2) presumes that it carries some information about comparison. It obviously doesn't. diff and rdiff sound better.

• Algorithm

  Reversal of the string just wastes time. You may work the same string from both directions simultaneously:

  for (int i = 1; i < s.length(); ++i) {
      diff = s.charAt(i) - s.charAt(i - 1);
      rdiff = s.charAt(s.length() - 1 - i) - s.charAt(s.length() - 1 - (i-1));
      ...
  

• Returning the comparison result is an anti-pattern.

  return stillEq;
  

  achieves the same result as

  if (stillEq)
      return true;
  else
      return false;
  

  in a much cleaner way.

• If you insist on reversing a string, better come up with an iterative method. Java cannot eliminate tail recursion.

Answer 2

What jumps out at me is:

private static String reverse (String s)
{
    if (s.length() > 0)
        return s.charAt(s.length()-1) + reverse(s.substring(0, s.length()-1));
    else
        return "";
}

This has two problems:

1. it's recursive - Java doesn't handle tail optimisation and recursion is slow
2. It makes a rather large number of copies - String.substring copies the underlying String
3. it's very long

I would suggest:

private static String reverse (final String s) {
    return new StringBuilder(s).reverse().toString();
}

I would also suggest that you always use brackets for your if...else statements. It's generally accepted common practice and with good reason - the few lines that you save by not doing so lead to some very insidious bugs.

On an algorithmic note: why reverse the String at all? Use one loop and read the String both forwards and backwards simultaneously.

For further improvement, walk through a comparison manually:

s = abcdef    
rs = fedcba

Leads to 5 distinct tests:

1. |b - a| == |e - f|
2. |c - b| == |d - e|
3. |d - c| == |c - d|
4. |e - d| == |b - c|
5. |f - e| == |a - b|

What do you notice about the pairs 1. <-> 5. and 2. <-> 4.? There is a simpler solution to this problem than brute force...

Answer 3

Your code is organized in a good way. Another thing I liked is that you have followed proper naming convention (i.e. Camel Case) while defining the function. However, there are few things that can be improved.

First of all, the code will give Compilation Error as the last } is missing in the code. Another thing is that, some imports like regex can be removed from the code as the functionality of those imports are never used in the code.

Another thing I have observed in your code that you are comparing both ascii values comp and comp2 and then returning the boolean after competing the for loop. Instead of that, you can return the false as soon as both ascii numbers are not same. This means we do not need to iterate through the whole string if a single difference doesn't match.

Apart from that, you have developed a function reverese to reverse the string and return the reversed string to the isFunny function. This thing (of passing a big string to the function, then doing some operation on each character and getting back into original one) can increase the time complexity as the maximum length of the string in this case can be 10000 (from description).

Actually, there is no need to reverse the String as the main goal is to compare ascii values of each character of two strings. We can directly get the ascii value of each character of reversed string without reversing the original String. So, my logic is as follows:

static boolean isFunny(String s) 
{
    int[] a1 = new int[s.length()];
    int[] a2 = new int[s.length()];
    int slen= s.length() - 1;

    for(int i = 0; i < a1.length; i++, slen--)
    {
        a1[i] = s.charAt(i);
        a2[slen] = s.charAt(i);
    }

    for(int i = 0; i < a1.length - 1; i++)
    {
        int diff1 = Math.abs(a1[i] - a1[i + 1]);
        int diff2 = Math.abs(a2[i] - a2[i + 1]);

        if(diff1 != diff2)
        {
            return false;
        }
    }

    return true;
}

Answer 4

In addition to the other answers.

• Let your IDE format your code instead of doing it by hand. This will avoid inconsistencies in spacing.
• Use an early return instead of the stillEq variable. This will make your program faster.
• Since the task talks about reading lines, you should use Scanner.nextLine instead of Scanner.next.
• Write i++ instead of ++i. While they are completely equivalent to the compiler, the former style is much more common. (Using the latter style tells the informed reader that you come from a C++ background and you don't trust the compiler to generate efficient code no matter how you write it.)

Answer 5

Learning from the answers above can the code be optimized further as

// Complete the funnyString function below

        static String funnyString(String s) {
        String rev = reverse(s);
        boolean stillEq = true;
        for (int i = 2; i < s.length() && stillEq; ++i)
        {
            int comp = (int)s.charAt(i) - (int)s.charAt(i-1);
            int comp2 = (int)rev.charAt(i) - (int)rev.charAt(i-1);
            stillEq = Math.abs(comp) == Math.abs(comp2);
        }
        if (stillEq) {
            return "Funny";
        }
        else{
            return "Not Funny";
        }
        }

        private static String reverse (String s)
        {
            if (s.length() > 0)
                return new StringBuilder(s).reverse().toString();
            else
                return "";
        }