Introduction

• a sequence of characters
• many tips that apply to arrays also apply to strings:
• common data structures for looking up strings:
  • Trie/Prefix Tree
  • Suffix Tree
• common string algorithms:
  • Rabin Karp for efficient searching of substring using a rolling hash
  • KMP for efficient searching of substring

Advantages

Disadvantages

Elements

Usages

Corner cases

• Empty string
• String with 1 or 2 characters
• String with repeated characters
• Strings with only distinct characters
• Ask about input character set and case sensitivity. Usually the characters are limited to lowercase Latin characters, for example a to z.
• Why use a 256 char array instead of a hashmap?
  • Simply put, arrays are a much simpler data structure. That means that the computer can manipulate them much faster and you will improve the efficiency of your code.
  • The one downside of course is that you may be allocating space that you don’t need. A hashmap only allocates space for the characters present in the string. However, this is a small price to pay and the array is a relatively small fixed size, so it is usually worth the cost.

Operations

Implementation

Complexity