Remove first character of string in O(1)

Question

How can I represent a string of characters in java so that removing the first character of string takes O(1) time?

This question: on string character removing talks about using substring to remove first character of string in Java. But as found here on Java 7 changes the substring implementation runs in O(length of string) now. How can I remove first character in O(1) using Java?

I just want an alternative if possible using any other similar classes like StringBuffer, StringBuilder etc. that deal with strings and chars. Or any other way, surely there must be a way to remove the first character of a word in O(1).

You can't, basically. Not if you want to get it as a `String`. — Jon Skeet, Sep 20 '16 at 09:18
Easy: write a different String class using the old trick. Or install an old JDK. The 1.0 was cute for example. — Denys Séguret, Sep 20 '16 at 09:19
I'm voting to close this question as off-topic because it wants to change the behavior of a method without changing the class — Denys Séguret, Sep 20 '16 at 09:20
@DenysSéguret I am not asking to use String class per se. Any other similar representation of a string is okay with me. I just discussed about substring method because it is one of the popular ways to get parts of a string. I am open to all other suggestions. — brijs, Sep 20 '16 at 09:30
If its OK to represent your string as an `ArrayDeque`, you can do it. I can’t believe I would ever do that, though. — Ole V.V., Sep 20 '16 at 09:37
@brijs If you want to change the representation, you can just take the code of the old String class. For most uses it's trivial. — Denys Séguret, Sep 20 '16 at 10:02

score 1 · Accepted Answer · answered Sep 20 '16 at 10:10

There is no way to get the characters of a String without first copying them, which takes O(n) time as it has to transverse the entire string to copy it... unless you use reflection.

Now you talk about replacing the first letter in the string and replacing the first letter of each word in the string interchangeably. If you want to replace the first letter of each word, you're going to have to transverse the entire string which is O(n) time - there is just no other way.

If you only want to replace the first letter, you can use reflection, but I wouldn't suggest you actually do this, rather just use .substring(String).

The method you're looking for:

/**
 * Replaces the first letter in a {@code String} in O(1) time.
 *
 * This uses reflection to change the values and will modify the
 * {@code String}s values. 
 *
 * @param str the {@code String} to modify.
 * @param letter the new first letter of the {@code String}.
 * @return {@code str}
 */
public static String replaceFirstLetter(String str, char letter) {
    if (str == null) {
        throw new NullPointerException("str cannot be null");
    }

    if (str.length() == 0) {
        throw new IllegalArgumentException("String cannot be empty");
    }

    try {
        Field value
                = str.getClass().getDeclaredField("value");

        value.setAccessible(true);

        Field modifiersField = Field.class.getDeclaredField("modifiers");
        modifiersField.setAccessible(true);
        modifiersField.setInt(value, value.getModifiers() & ~Modifier.FINAL);

        char[] values = (char[]) value.get(str);
        values[0] = letter;
        value.set(str, values);

    } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException ex) {
        ex.printStackTrace();
        //This should never happen
    }

    return str;
}

Note that this method will modify the String you pass in, so this breaks the immutable rule of the String class and should not be used in production code. Also, it will probably be quicker to just transverse the string than it will be to use this method.

public static void main(String[] args) {
    String s = "Hello";
    replaceFirstLetter(s, 'Y');
    System.out.println(s);

    System.out.println(replaceFirstLetter("Hello", 'G'));
}

This demonstrates it quite nicely.

Remove first character of string in O(1)

1 Answers1