Scala call length() on very long string throws exception: Maximum String literal length exceeded

Question

I wrote a scala solution for HackerRank BigSorting , and got RuntimeException in some test case. I tested the input in scastie, it seems the problem is caused by calling length() on a very long string, but the same java solution has no problem, is this a bug? my solution code is :

object Solution {
    def stringSort(x:String, y:String):Boolean = {
        var result = true

        if(x.length < y.length){
            result = true
        }else if(x.length > y.length){
            result = false
        }else{
            var founded = false
            var i = 0
            while(i < x.length && !founded){
                var xi = x.charAt(i)
                var yi = y.charAt(i)
                if(xi != yi){
                    result = xi < yi
                    founded = true
                }
                i += 1
            }
        }
        result
    }

    def bigSort(unsorted:Array[String]):Array[String] = {
        return unsorted.sortWith(stringSort)
    }

    def main(args: Array[String]) {
        val sc = new java.util.Scanner (System.in);
        var n = sc.nextInt();
        var unsorted = new Array[String](n);
        for(unsorted_i <- 0 to n-1) {
           unsorted(unsorted_i) = sc.next();
        }
        print(bigSort(unsorted).mkString("\n"))
        // your code goes here
    }
}

the exception is

java.lang.IllegalArgumentException: Maximum String literal length exceeded
    at scala.tools.asm.ByteVector.putUTF8(ByteVector.java:213)
    at scala.tools.asm.ClassWriter.newUTF8(ClassWriter.java:1114)
    at scala.tools.asm.ClassWriter.newString(ClassWriter.java:1582)
    at scala.tools.asm.ClassWriter.newConstItem(ClassWriter.java:1064)
    at scala.tools.asm.MethodWriter.visitLdcInsn(MethodWriter.java:1187)
    at scala.tools.asm.tree.LdcInsnNode.accept(LdcInsnNode.java:71)
    at scala.tools.asm.tree.InsnList.accept(InsnList.java:162)
    at scala.tools.asm.tree.MethodNode.accept(MethodNode.java:820)
    at scala.tools.asm.tree.MethodNode.accept(MethodNode.java:730)
    at scala.tools.asm.tree.ClassNode.accept(ClassNode.java:412)
...

java solution

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] unsorted = new String[n];
        for(int i = 0; i < n; i++) unsorted[i] = in.next();

        Arrays.sort(unsorted,new Comparator<String>() {
            @Override
            public int compare(String a, String b) 
            {
                return StringAsIntegerCompare(a,b);
            }
        });

        StringBuilder output = new StringBuilder("");
        for(String num : unsorted)
            output.append(num+"\n");
        System.out.println(output);
    }

    static int StringAsIntegerCompare(String s1, String s2)
    {
        if(s1.length() > s2.length()) return 1;
        if(s1.length() < s2.length()) return -1;
        for(int i = 0; i < s1.length(); i++)
        {
            if((int)s1.charAt(i) > (int)s2.charAt(i)) return 1;
            if((int)s1.charAt(i) < (int)s2.charAt(i)) return -1;
        }
        return 0;
    }
}

Answer 1

The only substantial difference between Java and Scala code that I can see is that Scala sortWith creates a new array, unlike Arrays.sort (and probably has some intermediate overhead too), so you could be running out of memory. You can instead try

import scala.math.Ordering
import scala.util.Sorting

val byLength: Ordering[String] = ... // your implementation, similar to Java comparator

Sorting.quickSort(unordered)(byLength) // instead of sortWith, sorts in-place

See http://www.scala-lang.org/api/2.12.0/scala/math/Ordering.html and http://www.scala-lang.org/api/2.12.0/scala/util/Sorting$.html for relevant documentation.

Answer 2

It is curious that a java solution, asking each string for its length, works while the Scala solution does not.

For what it's worth, the challenge is solvable without invoking the length method on any String element. I came up with an accepted solution (21 lines of code) using isDefinedAt() to determine the relative lengths of the String elements.

---

As requested, here is the solution I came up with.

For those not familiar with HackerRank challenges, the very poor Scala code in the main() method is supplied code (i.e. not my fault!). I wrote the sortum() code.

def sortum(arr:Array[String],start:Int = 0, end:Int = 1000000):Array[String] =
  if (arr.length < 2) arr             //only one of this length, return it
  else if (end-start < 1) arr.sorted  //multiple of the same length, sort them
  else {                              //partition into two groups
    val mid = (end-start)/2 + start
    val (a,b) = arr.partition(_.isDefinedAt(mid))
    if      (a.isEmpty) sortum(b,start,mid)
    else if (b.isEmpty) sortum(a,mid+1,end)
    else sortum(b,start,mid) ++ sortum(a,mid+1,end)
  }

def main(args: Array[String]) {
  val sc = new java.util.Scanner (System.in);
  var n = sc.nextInt();
  var unsorted = new Array[String](n);
  for(unsorted_i <- 0 to n-1) {
    unsorted(unsorted_i) = sc.next();
  }
  sortum(unsorted).foreach(println)
}

It's your basic binary search pattern used to segregate stings by their lengths.

---

Of course, now that we know that string .length isn't the source of the problem, a much simpler solution is available.

unsorted.map(_.length)  
        .zipWithIndex  
        .sortWith{case ((al,ax),(bl,bx)) =>
          al < bl || (al == bl && unsorted(ax) < unsorted(bx))
        }.foreach(x => println(unsorted(x._2)))