1

Say I have a big_string of length n and I want to remove a substring of length k from its end

we can do it as big_string[:-k], but this will be of O(n-k), can we do better than this, something like inO(k)?

sra1
  • 73
  • 1
  • 8
  • 4
    `big_string[:-k]` is not `O(n-k)`, what makes you think that? It's essentially a constant operation (`O(1)`) - either "write a null-terminator at this memory address", or "copy a defined amount of memory from one place to another and update a pointer" or some other thing that executes exactly once, regardless of the values of `n` or `k`. – Green Cloak Guy May 08 '19 at 19:55
  • 2
    List slicing is the idiomatic way to do this in python, and you're not really gonna find anything more efficient (or if you are, it'll be really ugly and non-pythonic). If you're looking for raw speed, use C or something. – Green Cloak Guy May 08 '19 at 19:56
  • 3
    https://stackoverflow.com/questions/35180377/time-complexity-of-string-slice – MyNameIsCaleb May 08 '19 at 20:01

1 Answers1

0

If your string is py2 unicode or py3 str, the memoryview idea that @MyNameIsCaleb pointed to won't work, and slices will indeed make copies, which is O(n).

Trimming the end is fast for mutable types (del m[-k:]), but only string types (which are immutable) support string operations like find(), in, and regular expressions.

If trimming the end is a very frequent operation, and using string operations is rare or can be bounded to a small portion of the string, it might be worth the trouble to convert the string once to a list of characters:

chars = [c for c in big_string]

To use string operations on bounded portions, you could convert a slice to a string. For example, to determine whether 'foo' occurs in the last 1000 characters:

'foo' in ''.join(chars[-1000:])

Adam M. Costello
  • 156
  • 1
  • 7