Modifying index of a string

Question

I am wondering about runtimes for replacing a character in a string (in javascript).

For example

let str = "hello world";
str[0] = "n";
console.log(str); // hello world

under strict mode, this throws an error because you cannot modify strings (read only).

How would you implement an O(1) time, O(1) space algorithm in js to do str[index] = char? In C, this is trivial because access is O(1) and you can modify that element without having to allocate a new array and copy values over.

I have found solutions using split to do this ... but isnt this overkill? That means O(n) time and space.

Wondering about this mostly for interview questions since I use javascript

wouldnt this be O(n) time? Since slice returns a shallow copy it is likely O(1) space at least. — , Apr 06 '19 at 05:05
but like, in the case where i would do `str[5] = "w"` or something, how does it go to 5 without traversing? Is slice an O(1) operation? On ECMA script it looks like O(n): http://www.ecma-international.org/ecma-262/6.0/index.html — , Apr 06 '19 at 05:10
@Iza For interview purposes probably no one will expect you to be optimizing the performance of string manipulation, since this is not usually a concern in the browser environment. Going into a JS interview and starting to mutate strings to improve the performance of a solution you're demonstrating is probably a good way to get disqualified. If you do need something like this you'd probably use arrays or typedarrays to represent the individual characters. — Asad Saeeduddin, Apr 06 '19 at 05:12
Thats definitely fair. I just feel like there should be ways to do these kinds of things. It makes analyzing my runtimes a lot harder when I write javascript code because I run into issues like this. So for now, there is no way to do this? Also I disagree that it would disqualify me. Every technical interview I have had, I've been asked to analyze or meet time / space requirements. If I am doing split or something in a for loop, I have to give my algorithm as O(n^2) as opposed to O(n) which is what is should be — , Apr 06 '19 at 05:13
@Iza The way to do this is to represent the string as an array of characters or bytes (depending on how far you want to go) and then mutate the array. In the normal case the farthest you need to go is `"n" + str.slice(1)`. — Asad Saeeduddin, Apr 06 '19 at 05:15
Maybe you can store your string as an array of characters, which has [O(1) access](https://stackoverflow.com/a/11535121/11168593) — jro, Apr 06 '19 at 05:19
Typically I've been been asked to analyze or meet time/space requirements over composite data, never individual characters of a string. I think it's strange for people to be asking you about the latter. You could of course as an academic exercise implement your own strings over raw byte arrays and start tuning the performance of those aggressively, but why stop there? Why not start asking interviewees to implement their own record types to substitute `{}`? If you're hiring them for a role with manual memory management this sort of stuff is relevant, in idiomatic JS not so much. — Asad Saeeduddin, Apr 06 '19 at 05:23
Putting this another way, the relevant input size for performance analysis in most JS applications is not usually the size of the strings in the program. — Asad Saeeduddin, Apr 06 '19 at 05:25
I can definitely agree with that. The main reason this is coming up - is because I have a repository full of algorithm questions with runtime analysis. And my runtimes and space complexities were always really bad... But it wasn't because my algorithm was wrong - it was because iI was using "inefficient" methods. So I wasn't sure If I should put what the runtime should be or what it actually is. Also, things like accessing a set is `o(n)` as opposed to `O(1)` so that typically increases runtime by a lot. These are pedantic issues, but they come up. I think in c++ accessing map is `O(logn)`. — , Apr 06 '19 at 06:18

score 0 · Answer 1 · answered Apr 06 '19 at 05:07

0

You can use the .replace("","") function.

Ex:

let str = "hello world"; 
str = str.replace("hello", "this");
console.log(str); // this world

Example codepen:https://codepen.io/darrow8/pen/VNjyJP

More info: https://www.w3schools.com/jsref/jsref_replace.asp

answered Apr 06 '19 at 05:07

Darrow Hartman

4,142
2
17
36

sure, but what if you want to replace at an index, not based on substring. Also, replace is definitely O(n) time, and likely O(n) space. – Apr 06 '19 at 05:08
I don't think it is possible to make this kind of function in O(1) time because you can have increasingly larger strings that the computer has to sort through – Darrow Hartman Apr 06 '19 at 05:10
why do you need to sort, this doesnt make sense. In C this is trivial in O(1) time. access is O(1) and thus setting is O(1) – Apr 06 '19 at 05:12

Shidersz · Answer 2 · 2019-04-06T05:34:45.383

In JavaScript, strings are immutable, so the best you can do is create a new string with the changes you need (so, forget about O(1)), the best I can think now is using the replacement function of string.replace():

const replaceAt = (str, idx, char) =>
{
    return str.replace(/./g, (match, offset) => offset === idx ? char : match);
}

console.log(replaceAt("Hello", 1, "3"));

Or, with String.slice():

const replaceAt = (str, idx, char) =>
{
    return str.slice(0, idx) + char + str.slice(idx + 1);
}

console.log(replaceAt("Hello", 1, "3"));

score 0 · Answer 3 · answered Apr 06 '19 at 05:33

You can use substring:

"use strict";
const replaceCharAt = (s, c, i) => i ? (i != 1 ? c + s.substring(i + 1) : s[0] + c + s.substring(3)) : c + s.substring(i);
let str = "hello world";
str = replaceCharAt(str, "n", 0);
str = replaceCharAt(str, "3", 1);
console.log(str);

Modifying index of a string

3 Answers3