Strings Interview Questions and Answers

A string is generally considered as a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures.

Problem

I have this string s1 = "My name is X Y Z" and I want to reverse the order of the words so that s1 = "Z Y X is name My" Is it possible to do it in-place (without using additional data structures) and with the time complexity being

O(n) ?

### Solution

Reverse the entire string, then reverse the letters of each individual word. After the first pass the string will be s1 = "Z Y X si eman yM" and after the second pass it will be s1 = "Z Y X is name My" Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Reversing the entire string is easily done in O(n) , and reversing each word in a string is also easy to do in O(n) .

O(n)+O(n) = O(n) . Space complexity is O(1) as reversal done

in-place. Implementation: CS static char[] ReverseAllWords(char[] in_text)

{
  int lindex = 0;
  int rindex = in_text.Length - 1;

  if (rindex > 1)
  {
    //reverse complete phrase
    in_text = ReverseString(in_text, 0, rindex);
    //reverse each word in resultant reversed phrase
    for (rindex = 0; rindex <= in_text.Length; rindex++)
    {
      if (rindex == in_text.Length || in_text[rindex] == ' ')
      {
        in_text = ReverseString(in_text, lindex, rindex - 1);
        lindex = rindex + 1;
      }
  }
}
return in_text;
}
static char[] ReverseString(char[] intext, int lindex, int rindex)
{
  char tempc;
  while (lindex < rindex)
  {
    tempc = intext[lindex];
    intext[lindex++] = intext[rindex];
    intext[rindex--] = tempc;
  }
return intext;
}

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation: ABC

// original string (3)

ABC ACB BAC BCA CBA CAB

// permutations 3! = 6

To print all permutations of a string use backtracking implemented via recursion: Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call. The base case is when the input is an empty string the only permutation is the empty string. In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

Complexity Analysis: Time Complexity: O(n!) Space Complexity: O(n!) For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!) . The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!) . Implementation: JS

// using backtracking
let permute = (str, left = 0, right = str.length - 1) => {
  //If left index is equal to right index
  //Print the string permutation
  if(left == right){
    console.log(str);
  }else{
    for(let i = left; i <= right; i++){
      //Swap the letters of the string
      str = swap(str, left, i);
      //Generate the permutation with swapped letters
      permute(str, left+1, right);
      //Restore the letters back to their position, e.q. backtrack to prev state of the string
      str = swap(str, left, i);
    }
}
}//Function to swap the letters of the string
let swap = (str, left, right) => {
  let arr = str.split('');
  [arr[left], arr[right]] = [arr[right], arr[left]];
  return arr.join('');
}
Java
public static void permutation(String str) {
  permutation("", str);
}
private static void permutation(String prefix, String str) {
  int n = str.length();
  if (n == 0) System.out.println(prefix);
  else {
    for (int i = 0; i < n; i++)
    // take new prefix from string[i], put it as a first element and construct the rest of the

    string
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
  }
}
PY
# using backtracking
def permute(a, l, r):
if l==r:
print toString(a)
else:
for i in xrange(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
# backtrack
# Driver program to test the above function
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

Immutability has several advantages, including (but not limited to): Programs with immutable objects are less complicated to think about, since you don't need to worry about how an object may evolve over time. You don't need to make defensive copies of immutable objects when returning or passing to other functions, since there is no possibility an immutable object will be modified behind your back. One copy of an object is just as good as another, so you can cache objects or re-use the same object multiple times. Immutable objects are good for sharing information between threads in a multi-threaded environment since they don't need to be synchronized and no locking shall be performed Operations on immutable objects return new immutable objects while operations that cause side-effects on mutable objects usually return void . This means several operations can be chained together. For instance

("foo" + "bar" + "baz").length()

In languages where functions are first class values, operations like map , reduce , filter , etc. are basic operations on collections. These can be combined in many ways, and can replace most loops in a program. Runtime safety. In some languages like Java strings are immutable and cannot be subclassed. This means that the Java runtime can pass around and receive strings from the user while guaranteeing that the string's value will remain constant. There are of course some disadvantages: Cyclic data structures such as graphs are difficult to build. If you have two objects which can't be modified after initialization, how can you get them to point to each other? Allocating lots and lots of small objects rather than modifying ones you already have can have a performance impact. Usually the complexity of either the allocator or the garbage collector depends on the number of objects on the heap. Naive implementations of immutable data structures can result in extremely poor performance. For instance, concatenating many immutable strings (like in Java) is O(n2) when the best algorithm is O(n) . It is possible to write efficient immutable data structures, it just takes a little more thought.

We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter. The counter will increase when it is ( and decrease when it is ) . Whenever the counter is negative, we have more ) than ( in the prefix. To make the prefix valid, we need to remove a ) . The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s. After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ) in two steps only with a different order. For this, we keep tracking the last removal position and only remove ) after that. Now one may ask. What about ( ? What if s = (()(() in which we need remove ( ? The answer is: do the same from right to left. However a cleverer idea is: reverse the string and reuse the code! Implementation: Java

public List<String> removeInvalidParentheses(String s) {
  List<String> ans = new ArrayList<>();
  remove(s, ans, 0, 0, new char[]{'(', ')'});
  return ans;
}
public void remove(String s, List<String> ans, int last_i, int last_j, char[] par) {
  for (int stack = 0, i = last_i; i < s.length(); ++i) {
    if (s.charAt(i) == par[0]) stack++;
    if (s.charAt(i) == par[1]) stack--;
    if (stack >= 0) continue;
    for (int j = last_j; j <= i; ++j)
    if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
    remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
    return;
  }
String reversed = new StringBuilder(s).reverse().toString();
if (par[0] == '(')
// finished left to right
remove(reversed, ans, 0, 0, new char[]{')', '('});
else
// finished right to left
ans.add(reversed);
}

A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction. You can check if a string is a palindrome by comparing it to the reverse of itself either using simpleloop or recursion. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n)

The time complexity is O(n/2) that is still

O(
n) . We doing n comparisons, where n = s.length() . Each
comparison takes
O(
1) time, as it is a single character comparison. You can cut the complexity of the function in
half by stopping at i == (s.length() / 2)+1 . It is not relevant in Big O terms, but it is still a pretty decent gain.

Loop approach has constant space complexity

O(
1) as we not allocating any new memory. Reverse string
approach needs
O(
n) additional memory to create a reversed copy of a string. Recursion approach has
O(
n)
space complexity due call stack.
Implementation:
Java
Loop:
boolean isPalindrome(String str) {
  int n = str.length();
  for( int i = 0; i < n/2; i++ )
  if (str.charAt(i) != str.charAt(n-i-1)) return false;
  return true;
}
Recursion:
private boolean isPalindrome(String s) {
  int length = s.length();
  if (length < 2) return true;
  return s.charAt(0) != s.charAt(length - 1) ? false :
  isPalindrome(s.substring(1, length - 1));
}

You may want to solve the problem by inverting the original string in a whole but note the space complexity will be worst than for the loop solution ( O(n) instead of O(1) ):

public static boolean isPalindrome(String str) {
  return str.equals(new StringBuilder(str).reverse().toString());
}
PY
str(n) == str(n)[::-1]
Explanation:

We're checking if the string representation of n equals the inverted string representation of n The [::-1] slice takes care of inverting the string After that, we compare for equality using ==

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation: ABC

// original string (3)

ABC ACB BAC BCA CBA CAB

// permutations 3! = 6

To print all permutations of a string use backtracking implemented via recursion: Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call. The base case is when the input is an empty string the only permutation is the empty string. In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

Complexity Analysis: Time Complexity: O(n!) Space Complexity: O(n!) For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!) . The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!) . Implementation: JS

// using backtracking
let permute = (str, left = 0, right = str.length - 1) => {
  //If left index is equal to right index
  //Print the string permutation
  if(left == right){
    console.log(str);
  }else{
    for(let i = left; i <= right; i++){
      //Swap the letters of the string
      str = swap(str, left, i);
      //Generate the permutation with swapped letters
      permute(str, left+1, right);
      //Restore the letters back to their position, e.q. backtrack to prev state of the string
      str = swap(str, left, i);
    }
}
}//Function to swap the letters of the string
let swap = (str, left, right) => {
  let arr = str.split('');
  [arr[left], arr[right]] = [arr[right], arr[left]];
  return arr.join('');
}
Java
public static void permutation(String str) {
  permutation("", str);
}
private static void permutation(String prefix, String str) {
  int n = str.length();
  if (n == 0) System.out.println(prefix);
  else {
    for (int i = 0; i < n; i++)
    // take new prefix from string[i], put it as a first element and construct the rest of the

    string
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
  }
}
PY
# using backtracking
def permute(a, l, r):
if l==r:
print toString(a)
else:
for i in xrange(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
# backtrack
# Driver program to test the above function
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

Strings can either be mutable or immutable. When a string is immutable it means that it's fixed allocated. So your string it's unique and can't be modified. If you change it, a copy of that string is created and the original string is deallocated instead. When a string is mutable it means that it's dynamically allocated, so your string can be modified.

Char arrays: Static-sized Fast access Few built-in methods to manipulate strings A char array doesn’t define a data type Strings: Slower access Define a data type Dynamic allocation More built-in functions to support string manipulations

A "string" is really just an array of char s; a null-terminated string is one where a null character '\0' marks the end of the string (not necessarily the end of the array). All strings in code (delimited by double quotes "" ) are automatically null-terminated by the compiler. So for example, "hi" is the same as {'h', 'i', '\0'} . Null-terminated strings are often a drain on performance, for the obvious reason that the time taken to discover the length depends on the length. The usual solution is to do both - keep the length and maintain the null terminator. It's not much extra work and means that you are always ready to pass the string to any function.

The followings are the steps to reversing a String using Stack:

1. String to char[] .
2. Create a Stack .
3. Push all characters, one by one.
4. Then Pop all characters, one by one and put into the char[] .
5. Finally, convert to the String . Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Implementation: Java public static String reverse(String str) {

char[] charArr = str.toCharArray();
int size = charArr.length;
Stack stack = new Stack(size);
int i;
for (i = 0; i < size; ++i) {
  stack.push(charArr[i]);
}
for (i = 0; i < size; ++i) {
  charArr[i] = stack.pop();
}
return String.valueOf(charArr);
}

Array-based strings have smaller overhead, so (for example) concatenation and split operations are faster on small datasets. However, when array-based strings are used for longer strings, time complexity and memory use for inserting and deleting characters becomes unacceptably large. In contrast, a rope data structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n) . From this, we can derive that ropes are more preferable when the size of our data is large and it is to be modified on a regular basis. String arrays perform better on smaller data & are better when there are less operations.

Suffix Tree is the way to go. If you analyze the output for the string "AAAAAAAAAAAAAA" , then there are

O(
n2) characters in it, so the
algorithm is at least
O(
n2) .

To achieve

O(
n2) , just build the suffix tree for each suffix of s (indices [1..n], [2..n], [3..n], ..., [n..n]). It

doesn't matter if one of the strings has no own end node, just count how often each node is used. At the end, iterate over each node with count > 1 and print its path. There are multiple way to construct the suffix tree:

1. Using Ukkonen's algorithm.
2. Using Suffix array and LCP (longest common prefix array)

Array-based strings have smaller overhead, so (for example) concatenation and split operations are faster on small datasets. However, when array-based strings are used for longer strings, time complexity and memory use for inserting and deleting characters becomes unacceptably large. In contrast, a rope data structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n) . From this, we can derive that ropes are more preferable when the size of our data is large and it is to be modified on a regular basis. String arrays perform better on smaller data & are better when there are less operations.

Boyer-Moore's approach is to try to match the last character of the pattern instead of the first one with the assumption that if there's not match at the end no need to try to match at the beginning. This allows for "big jumps" therefore BM works better when the pattern and the text you are searching resemble "natural text" (i.e. English). Scanning backwards with BM is faster because if you spot a character that isn't in the word, then you can skip many spaces forward. Best-case, you may only need to compare the last character every time, and skip forward the full length of the word. However, If you were scanning forward with KMP, and spotted the non-word character, then you can only skip forward as far as you have matched.

Knuth-Morris-Pratt searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. This means KMP is better suited for small sets like DNA (ACTG) however, there have been some modifications of BM that have made small-alphabet searching viable. BM can be faster or slower than KMP depending on the input, while KMP is perfectly reliable

O(
n) .

Things to note: KMP: Compares text left-to-right Uses a failure array to shift intelligently takes O(m) , where m is the length of the pattern, to compute failure array

takes O(m) , space
takes O(n) , time to search a string
BM:
Compares pattern from last character

Uses bad character jumps and good suffix jumps

takes O(m + size of alphabet) to compute tables
takes O(m + size of alphabet) , space
takes O(n) , but usually better to search

Space Usage favors Rabin-Karp One major advantage of Rabin-Karp is that it uses

O(
1) auxiliary storage space, which is great if the pattern

string you're looking for is very large. For example, if you're looking for all occurrences of a string of length 107 in a longer string of length 109, not having to allocate a table of 107 machine words for a failure function or shift table is a major win. Both Boyer-Moore and KMP use Ω(n) memory on a pattern string of length n, so Rabin-Karp would be a clear win here.

Rope is excellent if there are lots of prefixing and potentially better for

insertions; StringBuilders use continuous

memory, so only work efficiently for appending. StringBuilder is great for building strings by appending fragments - a very normal use-case. As developers need to do this a lot, StringBuilders are a very mainstream technology. Ropes are great for edit buffers, e.g. the data-structure behind, say, an enterprise-strength TextArea. So (a relaxation of Ropes, e.g. a linked list of lines rather than a binary tree) is very common in the UI controls world, but that's not often exposed to the developers and users of those controls. You need really really big amounts of data and churn to make the rope pay-off - processors are very good at stream operations, and if you have the RAM then simply realloc for prefixing does work acceptably for normal use-cases.

A Rope data structure is a tree data structure which is used to store or manipulate large strings in a more efficient manner. It allows for operations like insertion, deletion, search and random access to be executed faster and much more efficiently in comparison to a traditional String. More specifically a rope is a binary tree (that is, each node can have maximum of 2 children) where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. Nodes that are not leaf nodes do not hold an array of characters.

The insight behind Boyer-Moore is that if you start searching for a pattern in a string starting with the last character in the pattern, you can jump your search forward multiple characters when you hit a mismatch. Let's say our pattern p is the sequence of characters p1 , p2 , ..., pn and we are searching a string s , currently with p aligned so that pn is at index i in s . E.g.: s = WHICH FINALLY HALTS. AT THAT POINT... p = AT THAT

i = ^

The B-M paper makes the following observations: (1) if we try matching a character that is not in p then we can jump forward n characters: 'F' is not in p , hence we advance n characters: s = WHICH FINALLY HALTS. AT THAT POINT... p = AT THAT

i = ^
(2) if we try matching a character whose last position is k from the end of p then we can jump forward k
characters:

' 's last position in p is 4 from the end, hence we advance 4 characters:

s = WHICH FINALLY HALTS. AT THAT POINT... p = AT THAT

i = ^
Now we scan backwards from i until we either succeed or we hit a mismatch. (3a) if the mismatch occurs k
characters from the start of p and the mismatched character is not in p , then we can advance (at least) k
characters.
'L' is not in p and the mismatch occurred against p6 , hence we can advance (at least) 6 characters:
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
However, we can actually do better than this. (3b) since we know that at the old i we'd already matched some
characters (1 in this case). If the matched characters don't match the start of p , then we can actually jump
forward a little more (this extra distance is called 'delta2' in the paper):
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
At this point, observation (2) applies again, giving
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^

and bingo! We're done. Implementation: Java

public static int[] makeD1(char[] pat) {
  int[] table = new int[255];
  for (int i = 0; i < 255; i++)
  table[i] = pat.length;
  for (int i = 0; i < pat.length - 1; i++)
  table[pat[i]] = pat.length - 1 - i;
  return table;
}
public static boolean isPrefix(char[] word, int pos) {
  int suffixlen = word.length - pos;
  for (int i = 0; i < suffixlen; i++)
  if (word[i] != word[pos + i])
  return false;
  return true;
}
public static int suffix_length(char[] word, int pos) {
  int i;
  for (i = 0;
  ((word[pos - i] == word[word.length - 1 - i]) &&
  (i < pos)); i++) {}
  return i;

}
public static int[] makeD2(char[] pat) {
  int[] delta2 = new int[pat.length];
  int p;
  int last_prefix_index = pat.length - 1;
  for (p = pat.length - 1; p >= 0; p--) {
    if (isPrefix(pat, p + 1))
    last_prefix_index = p + 1;
    delta2[p] = last_prefix_index + (pat.length - 1 - p);
  }
for (p = 0; p < pat.length - 1; p++) {
  int slen = suffix_length(pat, p);
  if (pat[p - slen] != pat[pat.length - 1 - slen])
  delta2[pat.length - 1 - slen] = pat.length - 1 - p + slen;
}
return delta2;
}
public static int bm(char[] string, char[] pat) {
  int[] d1 = makeD1(pat);
  int[] d2 = makeD2(pat);
  int i = pat.length - 1;
  while (i < string.length) {
    int j = pat.length - 1;
    while (j >= 0 && (string[i] == pat[j])) {
      i--;
      j--;
    }
  if (j < 0)
  return (i + 1);
  i += Math.max(d1[string[i]], d2[j]);
}
return -1;
}

The KMP algorithm is an efficient string matching algorithm due to Donald Knuth, Vaughan Pratt, and James H. Morris. For the string matching problem (find p in S ) the naive approach would be to slide a window of size p all over S and check if it matches. That works but actually is inefficient. It takes

O(p*S) time.
Instead of naive approach KMP is a linear time (
O(
n) ) algorithm that exploits the observation that every time a
match (or a mismatch) happens, the pattern itself contains enough information to dictate where the new
examination should begin from. Every time the naive function fails (or succeeds), it starts matching over from

the next character. This might not be necessary. We could use our knowledge of the point of last matching and the "structure" of the test string to know where the next matching should begin from. How To Understand Prefix Function and Partial Match Table? The "structure" of the string is encapsulated in the Prefix (or Failure) Function that we use to create Partial Match Table. Now, in order to talk about the meaning, we need to know about proper prefixes and proper suffixes.

Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”. Proper suffix: All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”. Saying that here’s the partial match table for the pattern abababca where each cell value is "The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern". char: | a | b | a | b | a | b | c | a | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | Let’s also try it for cell five, which concerns “ababa”. We have four proper prefixes (“a”, “ab”, “aba”, and “abab”) and four proper suffixes (“a”, “ba”, “aba”, and “baba”). Now, we have two matches: “a” and “aba” are both proper prefixes and proper suffixes. Since “aba” is longer than “a”, it wins, and cell five gets value 3. How To Use Partial Match Table? We can use the values in the partial match table to skip ahead (rather than redoing unnecessary old comparisons) when we find partial matches. The formula works like this: If a partial match of length partial_match_length is found and table[partial_match_length] > 1 , we may skip ahead partial_match_length - table[partial_match_length - 1] characters.* Let’s say we’re matching the pattern “abababca” against the text “bacbababaabcbab”. Here’s our partial match table again for easy reference: char: | a | b | a | b | a | b | c | a | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | The first time we get a partial match is here: bacbababaabcbab | abababca This is a partial_match_length of 1. The value at table[partial_match_length - 1] (or table[0] ) is 0, so we don’t get to skip ahead any. The next partial match we get is here: bacbababaabcbab ||||| abababca

This is a partial_match_length of 5. The value at table[partial_match_length - 1] (or table[4] ) is 3. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 5 - table[4] or 5 - 3 or 2 ) characters:

// x denotes a skip
bacbababaabcbab
xx|||
abababca
This is a partial_match_length of 3. The value at table[partial_match_length - 1] (or table[2] ) is 1. That means
we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 3 - table[2] or 3 - 1 or 2 )
characters:
// x denotes a skip
bacbababaabcbab
xx|
abababca

At this point, our pattern is longer than the remaining characters in the text, so we know there’s no match. Things to remember: Once table is built, this algorithm has complexity O(n) even for binary alphabet (compare with O(mn) for brute force). Table is built very quickly at start since pattern is usually very small. Table-building part is O(m) . Search part is O(n) . Total complexity O(m+n) even on binary alphabet. Compare with O(mn) for brute force on binary alphabet. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Because the prefix-function already tells us what needs to be done about the already matched parts, we do not need to check those parts again and hence, only one pass over the string is sufficient. So, the time complexity of the matching is

O(
n) .
What about the pre-computation? It turns out that, if correctly implemented, it can be done in O(m) time

where m is a length of a pattern. Overall, it takes O(m+ n) time. But since m≤ n , the time is bounded by O(n) . This is certainly better than the usual

O(
n2)
We only require as much space as the pattern. So, the space requirement is O(m) .
Implementation:
Java
public static int KMP(String search, String target) {
  int[] failureTable = failureTable(target);
  int targetPointer = 0;
  // current char in target string
  int searchPointer = 0;
  // current char in search string
  while (searchPointer < search.length()) {
    // while there is more to search with, keep searching
    if (search.charAt(searchPointer) == target.charAt(targetPointer)) {
      // case 1

      // found current char in targetPointer in search string
      targetPointer++;
      if (targetPointer == target.length()) {
        // found all characters
        int x = target.length() + 1;
        return searchPointer - x;
        // return starting index of found target inside searched string
      }
    searchPointer++;
    // move forward if not found target string
  } else if (targetPointer > 0) {
    // case 2
    // use failureTable to use pointer pointed at nearest location of usable string prefix
    targetPointer = failureTable[targetPointer];
  } else {
    // case 3
    // targetPointer is pointing at state 0, so restart search with current searchPointer index
    searchPointer++;
  }
}
return -1;
}/**
* Returns an int[] that points to last valid string prefix, given target string
*/
public static int[] failureTable(String target) {
  int[] table = new int[target.length() + 1];
  // state 0 and 1 are guarenteed be the prior
  table[0] = -1;
  table[1] = 0;// the pointers pointing at last failure and current satte
  int left = 0;
  int right = 2;
  while (right < table.length) {
    // RIGHT NEVER MOVES RIGHT UNTIL ASSIGNED A VALID POINTER
    if (target.charAt(right - 1) == target.charAt(left)) {
      // when both chars before left and right

are equal, link both and move both forward

left++;
table[right] = left;
right++;
} else if (left > 0) {
  // if left isn't at the very beginning, then send left backward
  // by following the already set pointer to where it is pointing to
  left = table[left];
} else {
  // left has fallen all the way back to the beginning
  table[right] = left;
  right++;
}
}
return table;
}
PY
# Initialise array based on the failure function:
def init_arr(w):
m = len(w)
i = 0
j = 1# No proper prefix for string of length 1:
global arr
arr[0] = 0
while j < m:
if w[i] == w[j]:
i += 1
arr[j] = i
j += 1
# The first character didn't match:
elif i == 0:
arr[j] = 0
j += 1

# Mismatch after at least one matching character:
else:
i = arr[i - 1]
def kmp_search(w, s):
# Initialise array:
init_arr(w)# Initialising variables:
i = 0
j = 0
m = len(w)
n = len(s)# Start search:
while i < m and j < n:
# Last character matches -> Substring found:
if w[i] == s[j] and i == m - 1:

return True

# Character matches:
elif w[i] == s[j]:
i += 1
j += 1
# Character didn't match -> Backtrack:
else:
if i != 0:
i = arr[i-1]
else:
j += 1# Substring not found:

return False

Random read access becomes O(log n) Occupies greater overall storage space in comparison to a simple string, when not being operated upon, in order to store the parent nodes. However, this trade-off reduces as the string grows.

Increased complexity of structure creates a greater risk of bugs. Significantly slower on small strings. If you're looking at strings of 5-1000 characters, it probably doesn't improve the performance enough to be worth it. This is another case of a data structure that is designed for the 5% of people that have an extreme situation. Thread-safety code makes ropes much slower.

Ropes enable much faster insertion and deletion of text in comparison to string arrays, on which the operations have a time complexity of O(n) . For example strings concatenation function is able to work in constant time because, at most, it has to allocate a single concatenation node. Ropes do not require O(n) extra memory when being operated upon, unlike arrays which require it for copying operations. Ropes do not need large contiguous memory areas like arrays. If the operations performed are non-destructive (i.e the altered content is preserved) it behaves as a persistent data structure. This helps the text editors support multiple undo levels. Certain operations may reuse the previous rope sections to allow sharing in memory. Minor modifications of a rope can share memory with the original. Ropes are allocated in small chunks, significantly reducing memory fragmentation problems introduced by large blocks. Ropes allow deferred loading of substrings until required. Assignment is simply a (possibly reference counted) pointer assignment. Unlike reference-counted copy-on- write implementations, this remains largely true even if one of the copies is subsequently slightly modified. It is very inexpensive to checkpoint old versions of a string, e.g. in an edit history. Stable performance regardless of size.

A Rope data structure is a tree data structure which is used to store or manipulate large strings in a more efficient manner. It allows for operations like insertion, deletion, search and random access to be executed faster and much more efficiently in comparison to a traditional String. More specifically a rope is a binary tree (that is, each node can have maximum of 2 children) where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. Nodes that are not leaf nodes do not hold an array of characters.

Strings are immutable i.e., there are no methods defined that allow you to change (overwrite) or zero out the contents of a String after usage. Simply speaking here's no way (aside from reflection) you can get rid of the data before garbage collection kicks in. With an array, you can explicitly wipe the data after you're done with it. You can overwrite the array with anything you like, and the password won't be present anywhere in the system, even before garbage collection. Some information, such as Social Security numbers (SSNs) and passwords, is highly sensitive. This information should not be kept for longer than necessary nor where it may be seen, even by administrators. For instance, it should not be sent to log files and its presence should not be detectable through searches. Some transient data may be kept in mutable data structures, such as char arrays, and cleared immediately after use.

Pascal strings were made popular by one specific, but huge influential Pascal implementation, named UCSD. So UCSD Strings is a better term. In general it is not one specific type, but the basic principle of having the size prefixed to the character data. This makes getting the length a constant time operation O(1) instead of scanning the character data for a nul character. Pascal strings excel in... everything. NUL terminated strings save one to three bytes on short strings, which may have been useful in 1970 but isn't even worth mentioning today in virtually all circumstances. Aside from not being able to store a zero byte (which isn't too bad for text but rules out any kind of binary data), you can't determine string length efficiently. This affects a a good portion of string algorithms negatively. One example, in the comment you link to, is string comparison: If you have the length, you can instantly return false when comparing strings of different length.