Category: String

String

Index

  1. Definition
  2. Character at any index of string method
  3. Concatenation and Time complexity to concatenate
  4. Delete char at an index
  5. Reverse a string
  6. Sub-strings of a string
    • Definition sub-string
  7. Sub-sequence
    • Definition – sub-sequence
      • LCS

Definition – Array of character is String.

Accessing characters of char-Array i.e String:

stringVariable.charAt(index);

Imagine you were concatenating a list of strings, as shown below. What would the running time of this code be? For simplicity, assume that the strings are all the same length (call this x) and that there are n strings.

String joinWords(String[) words ) {
String sentence =
for(String w : words) {
sentence = sentence + w;
}
return sentence;
}

On each concatenation, a new copy of the string is created, and the two strings are copied over, character by character. The first iteration requires us to copy x characters, The second iteration requires copying 2x characters. The third iteration requires 3x, and so on. The total time therefore i s O ( x + 2x + . . . + n x ) .


This reduces to O( xn2 ) ,

Why is it O( x n2 ) ? Because 1 + 2 + . . . + n equals n( n + l ) / 2 , or O( n2 )

StringBuffer / StringBuilder

StringBuilder/StringBuffer can help you avoid above problem. StringBuilder simply creates a resizable array of all the strings, copying them back to a string only when necessary.

String joinWords(String[] words) {
StringBuilder sentence = new StringBuilder();
for (String w : words ) {
sentence.append(w);
}
return sentence.toString() ;
}

method to delete a character from StringBuffer

void deleteChar(String word) {
word=""Hello;
StringBuilder sb = new StringBuilder(word);
int i=0;
sb.deleteCharAt(i);
System.out.println(sb);
System.out.println(sb.length());

}

//Output- 
//ello
//4

Reverse the String

Solution – O(N) O(1)extra space –

  1. https://leetcode.com/problems/reverse-words-in-a-string-iii/discuss/1769521/Java-solution-using-two-pointers-approach
//Code -to list all substrings

//Practise link - https://leetcode.com/problems/reverse-words-in-a-string-iii/discuss/1769521/Java-solution-using-two-pointers-approach

Sub-Strings of a String

Definition – a sub-string refers to a contiguous sequence of characters within a larger string. More formally, a sub-string is any portion of a string that can be specified by indicating its starting and ending points.

Algorithm

  1. Brute-force -TC- O(N2) – Using – 2 iteration
    • iterate twice over string length – generating the sub-strings

Code

//Code -Brute-force -TC- O(N2) 
void generateSubstrings(String s){
int len=s.length;

for(int i=0;i<len;i++){
  for(int j=i+1;j<len;j++){
      s.substring(i,j);
     }
   }
}

Numerology Note:

  1. Total no of sub-string – n(n+1)/2
    • Here’s a breakdown of how the formula is derived:
      1. Substrings of length 1: There are nnn substrings (each character is a substring).
      2. Substrings of length 2: There are n−1n – 1n−1 substrings.
      3. Substrings of length 3: There are n−2n – 2n−2 substrings.
      4. And so on…
    • The total number of substrings is the sum of the first n natural numbers, which is given by the formula above i.e (n)+(n-1)+(n-2) +…+1=n(n+1)/2

Sub-sequence

Definition – a subsequence refers to a sequence derived from another sequence by deleting some or none of the elements without changing the order of the remaining elements.

Algorithm 1 – using brute force(bit masking/unmasking) – TC-2^n

//using brute force(bit masking/unmasking) - TC-2^n

Numerology Note:

  1. Total no of sub-sequence – N2 ,where N is length of string
    • Total Combinations: Since each element can be included or excluded independently of the others, the total number of possible combinations (subsequences) is the product of the choices for all elements.
    • 2×2×2×…×2 (n times)=2n