String

• a sequence of characters "abc"
• in java, they are objects

Creating Strings

• String literal a series of characters in your code that is enclosed in double quotes "abc"
• Whenever it encounters a string literal in your code, the compiler creates a String Object eith its value (really?)

    String s1 = "abc";
    String s2 = "abc";
    s1 == s2; // true

• Pooling for String objects Usually compiler and JVM will optimize for the number of String objects created, it will maintain an intern area in HEAP, for the same String literally it will only has one String object associated.

    String s1 = "abc";
    String s2 = new String("abc"); // new String 
    s1 == s2; // false

    String sa = "a";
    String sb = "b";
    String sab = "a" + "b"; //compile time concat

    sab == "a" + "b"; // true
    sab == sa + "b";  // false, sa.concat("b");
    sab == sa + sb;   // false
    // Optimization is at compile time!

    for (int i = 0; i < 100; i++) { 
        String s = new String("abc");
    }

    for (int i = 0; i < 100; i++) {
        String temp = "abc";
        String s = new String(temp);
    }

    // 100 : if "abc" is in the pool
    // 101 : if "abc" is not in the pool

String length

String Concat

s1 + s2 + s3 + s4 + ... + sn
suppose s1.length() = m
s1  + s2 -> s12   O(2*m)
s12 + s3 -> s123  O(3*m)
S123+ s4 -> s1234 O(4*m)
...

total time : O(2*m) + O(3*m) + ... + O(n*m) = O(n^2 *m)
     space : O(n^2 * m) 
 // Compile Optimization: could be further optimized to new StringBuilder().append()...

Programming Problems with String in Java

• The difference in that in Java, String is a wrapped class type

    - It is not a plain char array, the immutabiliti does not allow you to modify it
    - There are already a lot of useful methods defined in class String
    - There is a useful class StringBuilder representing "modifiable" String
  

We need to:

• Make the requirement clear, is it allowed to use some of the very efficient Java utilities

  1.String Builder? 2.existing in String? trim(), replece()..

• Usually Two strategies

  1. char[] array = input.toCharArray(), to do whatever we need to do on the char array, the new String(array)
  2. use StringBuilder builder, utilize the append(), deleteCharAt()...,either builder.toString(), new String(builder) will convert it back