Immutable String - Problem and Solutions

In C++ String is mutable , So there won't be any Problem.

But in Java String is immutable which creates problem and we have to resolve it .

So as String is immutable , If you want to change to change the String you have to create a new String even if you want to change one character .


So if we have to do String Concatenation in Java using '+' . It will take O(N*N) time .

String Concatenation is Slow in Java compared to C++ Which is not noticeable .

In Java Concatenation happens by first allocating enough space for new string and copy the contents from old string and append to the new String.

Time Complexity for a String of length 10 and n = 10000 is :


10+10* 2 +10 * 3 + ...... + 10 * n

= 10 * n * (n+1) / 2

Which will be O(N*N).

Example :

package com.techyield.operationsinarray;

public class StringConcatenation {

public static void main(String[] args) {

String s = "";

int n = 200000;

for(int i =0 ; i< n ;i++) {

s += "hello";

}

}

}

So you want to make String Immutable to Mutable :

Check here : https://techyield.blogspot.com/2019/06/string-immutable-to-mutable-java.html

String Immutable to Mutable (Java) Solutions

If you want your string to covert from Immutable to Mutable then better solution is :

Convert the String to CharArray :

package com.techyield.operationsinarray;

public class StringCharArray {

public static void main(String[] args) {

String s1 ="Sunny G";

char[] array = s1.toCharArray();

array[5] = ',';

System.out.println(array);

}

}

String Operations

String Operations :


Concatenation using '+'.


Position of First 'o' using indexOf().

Position of LastIndex of 'o' using lastIndexOf().

Getting Substring in a String using substring method substring(beginIndex , endIndex);

Example :


/**
 *
 */
package com.techyield.operationsinarray;

public class StringModification {

/**
* @param args
*/
public static void main(String[] args) {

String s1 = "Sunny";
s1+=" G";

System.out.println(s1);

System.out.println("The index of first n : "+s1.indexOf('n'));
System.out.println("The index of last n :"+s1.lastIndexOf('n'));

// Substring

System.out.println(s1.substring(2,7));
}

}

Output :

Sunny G

The index of first n : 2

The index of last n :3

nny G

Notes:

We should be aware of the time complexity of built in operations.

If the length of the string is N , the time complexity of both finding and substring operation is O(N).

Never forget the time complexity of the built-in operations into consideration when you are finding the time complexity of your solution.

String Immutable Or Mutable

Immutable means that we can't change the content of the String once it is initialized.

1. In C++ String is Mutable . Which means you can modify the String just like array.

2. In Java String is Immutable. Which will create problems so many problems , we can resolve with the help of converting String to CharArray or Using StringBuilder .

Testing on String By Modifying It :

/**
 *
 */
package com.techyield.operationsinarray;

/**
 * @author satyanarayanagokavarapu
 *
 */
public class StringModification {

/**
* @param args
*/
public static void main(String[] args) {

String s1 = "Sunny";

s1[4]=','; // It will show compile Time Error as This type of expression can be array type //can be resolved to String .

System.out.println(s1);

}

}

Introduction To String

String :

A String is an array of Unicode Characters. But like Array we can perform all the operations on String .

But there are some differences based on programming language.

Operations&Functions On Strings :

Compare Function :

String has its own compare function.

"==" Can be used in Java to compare whether the two objects are same but cannot be used to compare two Strings.

"==" Can be used in C++ to Compare Two Strings as it supports Operator Overloading.


Example :

package com.techyield.operationsinarray;

public class OperationsInString {

public static void main(String[] args) {

String s1 = "Hello World! Chitti Version 2.0";

// s2 is reference of s1

String s2 = s1;

// s3 is copy of s1

String s3 = new String(s1);

System.out.println("s1 is \""+s1+"\"");

System.out.println("s2 is "+s2);

System.out.println("s3 is "+s3);

// compare using ==

System.out.println("Compare Strings using \"==\"");

System.out.println("Comparing s1 and s2"+ (s1==s2));

System.out.println("Comparing s2 and s3 using \"==\""+ (s2==s3));

System.out.println("Comparing s1 and s3 using \"==\""+ (s1==s3));

// compare using equals method

System.out.println("Compare Strings using equals method");

System.out.println("Comparing s1 and s2"+ (s1.equals(s2)));

System.out.println("Comparing s2 and s3 using \"==\""+ (s2.equals(s3)));

System.out.println("Comparing s1 and s3 using \"==\""+ (s1.equals(s1)));

// compare using compareTo method

System.out.println("Compare Strings using compareTo method");

System.out.println("Comparing s1 and s2"+ (s1.compareTo(s2) == 0));

System.out.println("Comparing s2 and s3 using \"==\""+ (s2.compareTo(s3) == 0));

System.out.println("Comparing s1 and s3 using \"==\""+ (s1.compareTo(s1) == 0));

}

}

Introduction to 2D Array

Like in One Dimensional Array . Two Dimensional array also consists of sequence of elements.

But the elements can be laid in rectangular grid rather than a line.

We also have 2D Dynamic array Just as 1D Dynamic array https://techyield.blogspot.com/2019/06/introduction-to-dynamic-array.html

Let's take a look at an example of using a two-dimensional array:

package com.techyield.operationsinarray;

public class OperationsIn2Darray {

private static void printArray(int[][] a) {

for(int i =0; i < a.length; i++) {

         System.out.println(a[i]);

}

for(int i = 0 ; i< a.length; i++) {

for(int k=0; a[i]!= null && k < a[i].length; k++) {

System.out.println(a[i][k]+" ");

}

System.out.println();

}

}

public static void main(String[] args) {

System.out.println("Example I:");

int [][] a = new int[2][];

printArray(a);

System.out.println(" Example 2:");

int [][] b = new int[3][5];

printArray(b);

System.out.println("Example 3:");

b[0] = new int[3];

b[1] = new int[5];

printArray(b);

}

}

Introduction To Dynamic Array

In general Array has fixed capacity .  Array that we are talking about is linear array and we need to give size of the array when we initialize it  , which is wasteful and inconvenient sometimes.


Most programming languages offer built in dynamic array. Which is a random access list data structure with variable size .

We have ARRAYLIST in Java which is similar to Vector C++.

/**
 *
 */
package com.techyield.operationsinarray;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class OperationsInDynamicArray {

/**
* @param args
*/
public static void main(String[] args) {
       
// Initialize
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 ; // here l2 == null

// Cast an array to List
Integer[] array = {1,2,3,4,5,6,7,8};
l2 = new ArrayList<>(Arrays.asList(array));

// Make a copy

List<Integer> l3 = l2;  // another reference to l1
List<Integer> l4 = new ArrayList<>(l2); // make an actual copy of l2

// Length

System.out.println("The size of list is "+l2.size());

// Access Element
System.out.println("The first element in l2 is "+l2.get(0));

// Iterate the linkedList
System.out.println("The contents of l2 are : ");
for(Integer a : l2) {
System.out.println(a);
}
System.out.println(" Version2 ............");
for(int i =0 ; i < l2.size(); i++) {
System.out.println(" "+l2.get(i));
}
System.out.println();

// Modify the element
l2.set(0,5);
System.out.println("l2.get(0)"+l2.get(0));
// Modify the element
l2.set(0, -1);
System.out.println("l2.get(0)"+l2.get(0));
// here l3 refers to l2 so modifying l2 modifies l3
// Sort
Collections.sort(l2);
// Add a new element at the end of the ArrayList
l2.add(9);

l2.add(2,5);

// Remove an element

l2.remove(l2.size()-1);

for(int u : l2) {
System.out.println(u);
}




}

}