Skip to main content
Code Review

Return to Answer

Suggest how to achieve O(N) time complexity.
Source Link
edit approved Sep 15, 2014 at 13:55
Community Bot
edit approved Sep 15, 2014 at 13:55
Community Bot
  • 1

You could

  • put the chars in the to-be-deleted into a char array and sort them. This would allow you to look up characters via a binary search.
  • Use a StringBuilder to create the string of characters to keep.

This would be O(N) for space and O(N * log N) for computation time. You can reduce it to O(N) for time by using a bitset of the characters to remove instead of using a binary search.

You could

  • put the chars in the to-be-deleted into a char array and sort them. This would allow you to look up characters via a binary search.
  • Use a StringBuilder to create the string of characters to keep.

This would be O(N) for space and O(N * log N) for computation time. You can reduce it to O(N) for time.

You could

  • put the chars in the to-be-deleted into a char array and sort them. This would allow you to look up characters via a binary search.
  • Use a StringBuilder to create the string of characters to keep.

This would be O(N) for space and O(N * log N) for computation time. You can reduce it to O(N) for time by using a bitset of the characters to remove instead of using a binary search.

Post Migrated Here from stackoverflow.com (revisions)
Source Link
Peter Lawrey
Peter Lawrey
  • 718
  • 3
  • 7

You could

  • put the chars in the to-be-deleted into a char array and sort them. This would allow you to look up characters via a binary search.
  • Use a StringBuilder to create the string of characters to keep.

This would be O(N) for space and O(N * log N) for computation time. You can reduce it to O(N) for time.