169

I'm trying The Next Palindrome problem from Sphere Online Judge (SPOJ) where I need to find a palindrome for a integer of up to a million digits. I thought about using Java's functions for reversing Strings, but would they allow for a String to be this long?

Improve this question
3
  • are you saying that you need to write a function that generates palindromes, the size of which is user specified and can be up to 1 million characters in length? Commented Jul 24, 2009 at 20:29
  • 4
    The Problem (from SPOJ) may contain a 100Gigabyte file, and you like to load it into a string at once? Seriously... please use a Scanner! Commented Feb 17, 2015 at 14:11
  • Possible duplicate of String's Maximum length in Java - calling length() method Commented Jun 16, 2017 at 5:55

7 Answers 7

Reset to default
257

You should be able to get a String of length

  1. Integer.MAX_VALUE always 2,147,483,647 (231 - 1)
    (Defined by the Java specification, the maximum size of an array, which the String class uses for internal storage)
    OR

  2. Half your maximum heap size (since each character is two bytes) whichever is smaller.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

... or your maximum heap size divided by 2 ... since character is 2 bytes
how do I find out the maximum heap size? Also, I don't know which java virtual machine the judge is using to test my problem is Integer.MAX_VALUE part of the spec of JVM dependant?
Integer.MAX_VALUE is always 2147483647 (2^31 - 1), that's part of the Java Specification.
Assuming a 64-bit JVM, since you'd need 8GB of virtual memory to store a string of that length.
Java 9 is going to use a single byte per character for strings having only iso-latin-1 content, so such strings can have as many characters as the heap in bytes (or max array length, whatever is smaller), but on the other hand, since non-latin strings use two bytes in an array, the maximum string length will be halved for them in Java 9, only supporting 1073741823 characters.
|
21

I believe they can be up to 2^31-1 characters, as they are held by an internal array, and arrays are indexed by integers in Java.

Improve this answer

2 Comments

The internal implementation is irrelevant - there's no reason why the character data couldn't be stored in an array of longs, for instance. The problem is the interface uses ints for length. getBytes and similar may have problems if you try for a very large string.
That is true - I was implying that fact. My bad.
16

While you can in theory Integer.MAX_VALUE characters, the JVM is limited in the size of the array it can use.

public static void main(String... args) {
    for (int i = 0; i < 4; i++) {
        int len = Integer.MAX_VALUE - i;
        try {
            char[] ch = new char[len];
            System.out.println("len: " + len + " OK");
        } catch (Error e) {
            System.out.println("len: " + len + " " + e);
        }
    }
}

on Oracle Java 8 update 92 prints

len: 2147483647 java.lang.OutOfMemoryError: Requested array size exceeds VM limit
len: 2147483646 java.lang.OutOfMemoryError: Requested array size exceeds VM limit
len: 2147483645 OK
len: 2147483644 OK

Note: in Java 9, Strings will use byte[] which will mean that multi-byte characters will use more than one byte and reduce the maximum further. If you have all four byte code-points e.g. emojis, you will only get around 500 million characters

Improve this answer

2 Comments

Compact Strings in Java 9 use either Latin-1 or UTF-16 encoding. No variable length encoding, that is, no three byte characters.
@apangin "It is not a goal to use alternate encodings such as UTF-8" thank you for the correction.
5

Have you considered using BigDecimal instead of String to hold your numbers?

Improve this answer

2 Comments

It depends on what the application is going to do with the numbers. If it is going to just do textual things like finding palindromes, counting (decimal) digits, then a String is better. If it is going to be doing arithmetic, a BigDecimal (or BigInteger) is better.
The problem is "For each K, output the smallest palindrome larger than K." (where K is the number given). It would be trivially simple to output the first palindrome smaller than K. You require arithmetic to find one larger than K. Example: Find the next palindrome larger than 999999999999, or the next palindrome larger than 12922.
4

Integer.MAX_VALUE is max size of string + depends of your memory size but the Problem on sphere's online judge you don't have to use those functions

Improve this answer

Comments

3

Java9 uses byte[] to store String.value, so you can only get about 1GB Strings in Java9. Java8 on the other hand can have 2GB Strings.

By character I mean "char"s, some character is not representable in BMP(like some of the emojis), so it will take more(currently 2) chars.

Improve this answer

1 Comment

Could you attach reference for Java-9 limiting String size to 1 GB from 2 GB
-1

The heap part gets worse, my friends. UTF-16 isn't guaranteed to be limited to 16 bits and can expand to 32

Improve this answer

2 Comments

Except Java's char type is 16 bits exactly, so the number of bits UTF-16 uses doesn't really matter...
@awksp: char is 16 bits, but a character in a String can occupy two char's (two 'surrogate' code elements to represent one character in UTF16). However, the Q was only for decimal digits and these are not only BMP but 8859-1/block0 and ASCII.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.