reduce an array of strings to have no duplicates or substrings

Question

Given an array of

['/a','/a/b/c/d/e','/b','/b/c','/a/b/c/d','/a','/b']

I would like to be able to reduce this array down to:

['/a/b/c/d/e','/b/c']

i.e the longest of each unique path ('/a' is a substring of '/a/b/c/d/e')

Perhaps I don't know the correct terminology, but I've been Googling for a couple of hours and have gotten nowhere

I was thinking of sorting by element length, then for each element loop through the list, checking the indexOf() until I reached the element itself

Just seems kind of expensive.

edit I didn't explain that well enough - the strings are paths - and I need to use mkdirp to create the directory structure, but didn't want to call it many times (mkdir /a/b/c/d/e will create /a/b/c , so if I have another path of /a/b/c I just want to ignore it

Possible duplicate of [Remove Duplicates from JavaScript Array](http://stackoverflow.com/questions/9229645/remove-duplicates-from-javascript-array) — James Gould, Mar 21 '17 at 15:09
`/b/c` is a substring of `/a/b/c/d/e` - what makes it special enough to get its own result? — Jamiec, Mar 21 '17 at 15:11
yeah, I didn't explain that well enough - the strings are paths - and I need to use mkdirp to create the directory structure, but didn't want to call it many times. So in this case /b/c is a folder structure. Sorry about that. — jmls, Mar 21 '17 at 15:12
This is where you're better off asking the "real" question, rather than an abstract version of it. — Jamiec, Mar 21 '17 at 15:15
@JayGould : yes, I can easily remove duplicates (esp with set() ) but that doesn't help with removing /a/b/c if I have /a/b/c/d/e as they are not duplicates. Thanks for the link though, it's useful — jmls, Mar 21 '17 at 15:15

Anish Goyal · Answer 1 · 2017-03-21T15:35:08.543

I would sort the array. Then, iterate through. For each element, if it is equivalent to the next element, or a substring of it, skip it. Otherwise, add it to a dynamically growing structure. Finally, convert your dynamically growing structure to an array.

You only have to check the next item since anything that's a prefix of something else will come alphabetically before it, directly before the shortest string using it as a prefix. This cuts your algorithm down to O(nlgn).

Luckily, '/' comes before letters and numbers in ASCII, which will help you extend this to paths with multiletter folder names.

Let's assume your original array is in arr.

var arr = ['/a','/a/b/c/d/e','/b','/b/c','/a/b/c/d','/a','/b'];
arr.sort();
var output = [];
for(var i = 0; i < arr.length; i++)
{
  if(i < arr.length - 1 && arr[i + 1].indexOf(arr[i]) == 0 &&
    (arr[i].length == arr[i + 1].length || arr[i + 1].charAt(arr[i].length) == "/"))
  {
    continue;
  }
  output.push(arr[i]);
}
console.log(output);

In the for loop, for each string we check if there's another string in the array after it; if not, that string is not a prefix of another path. Then, we check if the current and next strings are equal. If not, we check if the next string starts with the current one, and also if the next character after the current string is a "/" in the next string so that we don't assume "abc/def" is a prefix of "abc/defghi/jkl", which are clearly two separate paths.

Thank you sir for turning the code into a snippet @Jamiec :) — Anish Goyal, Mar 21 '17 at 15:37

Nina Scholz · Answer 2 · 2017-03-21T16:03:24.900

You could check the whole string and collect the longer ones, without sorting in advance.

var array = ['/abc/def', '/abc/defghi/jkl', '/a', '/a/b/c/d/e', '/b', '/b/c', '/efg', '/a/b/c/d', '/a', '/b', '/a/b'],
    result = array.reduce(function (r, a) {
        r.some(function (b, i, rr) {
            var aa = a + '/',
                bb = b + '/',
                min = Math.min(aa.length, bb.length);

            if (aa.slice(0, min) === bb.slice(0, min)) {
                if (a.length > b.length) {
                    rr[i] = a;
                }
                return true;
            }
        }) || r.push(a);
        return r;
    }, []);
    
console.log(result);

score 0 · Answer 3 · answered Mar 21 '17 at 15:48

0

I eventually came up with this - would appreciate comments

let originalArray = ['/abc/def','/abc/defghi/jkl','/a','/a/b/c/d/e','/b','/b/c','/efg','/a/b/c/d','/a','/b','/a/b'];

let uniqueArray = Array.from(new Set(originalArray));
let newArray = [];

uniqueArray.sort();

uniqueArray.forEach((item,index) => {
  if (index === uniqueArray.length - 1) {
      newArray.push(item);
      return;
  }

  if (uniqueArray[index + 1].indexOf(item + "/") === -1) {
      newArray.push(item);
  }
});

console.log(newArray)

answered Mar 21 '17 at 15:48

jmls

2,879
4
34
58

checking if indexOf returns -1 may not be what you want, because what if indexOf returns greater than 0? in that case, you would skip a valid path. – Anish Goyal Mar 21 '17 at 19:15
I do want -1 : if there is no match on the next entry, then the current entry is unique. if it's >0 it matches, so I skip it – jmls Mar 21 '17 at 20:32
But then you have "/b/a/d".indexOf("/a/d") = 2 which is greater than 0. However, it's not a prefix of "/b/a/d" so per your description, it should be kept. Your method will not keep it though, since indexOf is not returning -1. – Anish Goyal Mar 21 '17 at 20:41
damn! yes. I probably should be using startsWith instead. thanks ! – jmls Mar 22 '17 at 11:27

reduce an array of strings to have no duplicates or substrings

3 Answers3