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?
-
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?– RobertJul 24, 2009 at 20:29
-
3The Problem (from SPOJ) may contain a 100Gigabyte file, and you like to load it into a string at once? Seriously... please use a Scanner!– GrimFeb 17, 2015 at 14:11
-
Possible duplicate of String's Maximum length in Java - calling length() method– BergiJun 16, 2017 at 5:55
7 Answers
You should be able to get a String of length
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)
ORHalf your maximum heap size
(since each character is two bytes) whichever is smaller.
-
43... or your maximum heap size divided by 2 ... since character is 2 bytes Jul 24, 2009 at 20:29
-
2how 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? Jul 24, 2009 at 20:40
-
6Integer.MAX_VALUE is always 2147483647 (2^31 - 1), that's part of the Java Specification.– cd1Jul 24, 2009 at 20:45
-
5Assuming a 64-bit JVM, since you'd need 8GB of virtual memory to store a string of that length. Jul 24, 2009 at 20:59
-
3Java 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.– HolgerJul 14, 2017 at 15:35
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.
-
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. Jul 24, 2009 at 20:45 -
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
-
2Compact Strings in Java 9 use either Latin-1 or UTF-16 encoding. No variable length encoding, that is, no three byte characters.– apanginDec 8, 2016 at 7:49
-
@apangin "It is not a goal to use alternate encodings such as UTF-8" thank you for the correction. Dec 8, 2016 at 8:05
Have you considered using BigDecimal
instead of String
to hold your numbers?
-
1It 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. Jul 25, 2009 at 0:54
-
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. Jul 25, 2009 at 6:48
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
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.
-
4Could you attach reference for Java-9 limiting String size to 1 GB from 2 GB May 24, 2018 at 6:07
The heap part gets worse, my friends. UTF-16 isn't guaranteed to be limited to 16 bits and can expand to 32
-
2Except Java's
char
type is 16 bits exactly, so the number of bits UTF-16 uses doesn't really matter...– awkspJul 9, 2014 at 19:23 -
@awksp:
char
is 16 bits, but a character in aString
can occupy twochar
'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. Oct 9, 2020 at 15:33