Strings

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.