https://twitter.com/shelajev/status/899636401595187200

LukasChallenge.java

package org.shelajev;

import java.util.ArrayList;
import java.util.List;

public class LukasChallenge {

  public static void main(String[] args) {
    LukasChallenge lukasChallenge = new LukasChallenge();
    List<Pair> aaa = lukasChallenge.subPalindromes("ababa");
    System.out.println(aaa);
    System.out.println(aaa.size());
  }

  public List<Pair> subPalindromes(String s) {
    int n = s.length();
    int[] d1 = new int[n];
    int[] d2 = new int[n];

    char[] chars = s.toCharArray();

    int l = 0, r = -1, k;
    for(int i = 0; i < n; i++){
      if(i > r) k = 1;
      else k = min(d1[l + r - i], r - i);

      while(0 <= i - k && i + k < n && chars[i - k] == chars[i + k]) k++;
      d1[i] = k;
      if(i + k - 1 > r) {
        r = i + k - 1;
        l = i - k + 1;
      }
    }

    l = 0; r = -1;
    for(int i = 0; i < n; i++){
      if(i > r) k = 0;
      else k = min(d2[l + r - i + 1], r - i + 1);

      while(i + k < n && i - k - 1 >= 0 && chars[i+k] == chars[i - k - 1]) k++;
      d2[i] = k;

      if(i + k - 1 > r) {
        l = i - k;
        r = i + k - 1;
      }
    }

    List<Pair> returnMe = new ArrayList<Pair>();
    for(int i = 0; i < n; i++) {
      int c = d1[i];
      while(c > 0) {
        returnMe.add(new Pair(i - (c-1), i + (c-1)));
        c--;
      }
      c = d2[i];
      while(c > 0) {
        returnMe.add(new Pair(i - c, i + (c-1)));
        c--;
      }
    }

    return returnMe;
  }

  int min(int a, int b) {
    return a < b ? a : b;
  }

}

class Pair {
  int i, j;

  Pair(int a, int b) {
    this.i = a;
    this.j = b;
  }

  @Override public String toString() {
    return "(" + i + "; " + j + ")";
  }
}