java.lang.StringIndexOutOfBoundsException: String index out of range: -1 (Works with another program)

Question

I'm supposed to create a program that finds the longest palindrome in a DNA string. Unlike a regular palindrome program, this one requires A to match with T and C to match with G (so instead of 1221 we'd have TCGA for example). After trying myself I did find a very good program for the normal palindrome problem, the one on this website: http://www.journaldev.com/530/java-program-to-find-out-longest-palindrome-in-a-string

I then tried to modify it to fit my needs. Basically the changes I made were the following:

1. Instead of those strings shown in the example, I read a string from the argument line. The string is the following DNA sequence (although I tested the program with only parts of it):

http://introcs.cs.princeton.edu/java/31datatype/genomeVirus.txt

2. Instead of the command

    while (left >= 0 && right < s.length()
               && s.charAt(left) == s.charAt(right)) {
           left--;
           right++;
       }
   

I did:

while (left >= 0 && right < s.length()
&& s.charAt(left) == 'A' && s.charAt(right) == 'T' || s.charAt(left) == 'T' && s.charAt(right) == 'A'
|| s.charAt(left) == 'G' && s.charAt(right) == 'C' || s.charAt(left) == 'C' && s.charAt(right) == 'G')
   {
 left--;
 right++;

(Full code below)

However, when I try this program on a string, I always get the error:

java.lang.StringIndexOutOfBoundsException: String index out of range: -1
    at java.lang.String.substring(Unknown Source)
    at LongestPalindrome.intermediatePalindrome(LongestPalindrome.java:17)
    at LongestPalindrome.longestPalindromeString(LongestPalindrome.java:26)
    at LongestPalindrome.main(LongestPalindrome.java:5)

I just don't get it! I don't realize how I'm getting out of the string, when I try the original program I linked to, it always works with no matter which string. I feel like I'm doing everything correctly, simply replacing the == command with various scenarios that should make sense.

I figured it might have something to do with

return s.substring(left+1, right);"

I tried to take the +1 away but it seems to ruin the whole deal. I just don't realize how I'm going out of the string, since it worked perfectly before my adjustments.

Any help would be greatly appreciated! Below is the code!

public class LongestPalindrome {

 public static void main(String[] args) {
   String gen = new String(args[0]);
   System.out.println(longestPalindromeString(gen));
 }

 static public String intermediatePalindrome(String s, int left, int right)     {
  if (left > right) return null;
  while (left >= 0 && right < s.length()
    && s.charAt(left) == 'A' && s.charAt(right) == 'T' || s.charAt(left) == 'T' && s.charAt(right) == 'A'
|| s.charAt(left) == 'G' && s.charAt(right) == 'C' || s.charAt(left) == 'C' && s.charAt(right) == 'G')
       {
   left--;
   right++;
  }
  return s.substring(left+1, right);
 }

 // O(n^2)
 public static String longestPalindromeString(String s) {
  if (s == null) return null;
  String longest = s.substring(0, 1);
  for (int i = 0; i < s.length() - 1; i++) {
   //odd cases like 121
   String palindrome = intermediatePalindrome(s, i, i);
    if (palindrome.length() > longest.length()) {
    longest = palindrome;
   }
   //even cases like 1221
   palindrome = intermediatePalindrome(s, i, i + 1);
   if (palindrome.length() > longest.length()) {
    longest = palindrome;
   }
  }
  return longest;
 }

}

Answer 1

1. You are calling it with right == 0. You need to change the first call to:

    String palindrome = intermediatePalindrome(s, i, i+1)
   

2. Operator precedence problem. You've added some || conditions which are also evaluated even if the range checks fail. It should be:

   while (left >= 0 && right < s.length()
   && (s.charAt(left) == 'A' && s.charAt(right) == 'T'
       || s.charAt(left) == 'T' && s.charAt(right) == 'A'
       || s.charAt(left) == 'G' && s.charAt(right) == 'C'
       || s.charAt(left) == 'C' && s.charAt(right) == 'G'))
   

Note the parentheses around the entire second operand of the second &&.