Find the longest string in a nested array using Recursion in Javascript?

Question

I have seen various answers which give a solution to finding the longest string in an array. My problem is, I want to find the longest string in a nested array. The nesting level may be of N-levels or just two levels deep. My initial solution is as follows:

    let myArray = [
    'ABC',
    'ABCD',
    'ABCDE',
    [
      'ABC',
      'ABCABABA',
      [
        'ABABABABABABABABAZZ'
      ],
    'ABCABABASS',

     ],
   'ABCDEFGH',
   'ABABABABZZQ'
   ]

function longestString(arr) {
let longestStr = ''
arr.forEach(item => {
if(typeof item === 'string') {
  if(item.length > longestStr.length) {
    longestStr = item;
    console.log('Longest Item', item);
  }    
} else {
    longestString(item)
  }
})
 return longestStr;
}

console.log(longestString(myArray))

Observed Output -> ABABABABZZQ

Expected Output -> 'ABABABABABABABABAZZ'

What is the tweak needed to print only the longest string?

The problem is that you are printing inside longestString. Instead, each iteration of the function should just return the longest string found, and when calling recursively, you should compare the returned value to the current stored longest string. — Matt
– Matt, Commented Nov 11, 2018 at 5:37
An equivalent solution to @Matt would be to pass the current longestStr as a parameter to the function so your can always compare the new strings to it. (Posted an answer here if it's not clear) — Nirit Levi
– Nirit Levi, Commented Nov 11, 2018 at 6:49

CertainPerformance · Accepted Answer · 2018-11-11 05:46:23Z

You need to use the return value of the recursive call - put the returned string through the same test that you put the item through, check if it's longer than longestStr, and if so, reassign longestStr:

let myArray = [
  'ABC',
  'ABCD',
  'ABCDE', [
    'ABC',
    'ABCABABA', [
      'ABABABABABABABABAZZ'
    ],
    'ABCABABASS',

  ],
  'ABCDEFGH',
  'ABABABABZZQ'
]

function longestString(arr) {
  let longestStr = ''
  arr.forEach(item => {
    if (typeof item === 'string') {
      if (item.length > longestStr.length) {
        longestStr = item;
      }
    } else {
      const nestedLongest = longestString(item);
      if (nestedLongest.length > longestStr.length) {
        longestStr = nestedLongest;
      }
    }
  })
  return longestStr;
}

console.log(longestString(myArray))

Or, to be somewhat more DRY:

const myArray=['ABC','ABCD','ABCDE',['ABC','ABCABABA',['ABABABABABABABABAZZ'],'ABCABABASS',],'ABCDEFGH','ABABABABZZQ']

function longestString(arr) {
  let longestStr = '';
  const check = str => {
    if (str.length > longestStr.length) longestStr = str;
  };
  arr.forEach(item => {
    check(typeof item === 'string' ? item : longestString(item));
  });
  return longestStr;
}

console.log(longestString(myArray))

Another option would be to have an inner function that gets called, while assigning to a longestStr variable that's persistently in scope until the end of the longestString function - meaning that you don't have to worry about the results of the recursive calls:

const myArray=['ABC','ABCD','ABCDE',['ABC','ABCABABA',['ABABABABABABABABAZZ'],'ABCABABASS',],'ABCDEFGH','ABABABABZZQ']

function longestString(input) {
  let longestStr = '';
  const check = str => {
    if (str.length > longestStr.length) longestStr = str;
  };
  function recursiveFn(arr) {
    arr.forEach((item) => {
      if (typeof item === 'string') check(item)
      else recursiveFn(item);
    });
  }
  recursiveFn(input);
  return longestStr;
}

console.log(longestString(myArray))

Ori Drori · Accepted Answer · 2018-11-11 05:38:58Z

1

Use Array.flat() to flatten the array, and then use Array.reduce() to find the longest item:

const myArray = [
  'ABC',
  'ABCD',
  'ABCDE', [
    'ABC',
    'ABCABABA', [
      'ABABABABABABABABAZZ'
    ],
    'ABCABABASS',

  ],
  'ABCDEFGH',
  'ABABABABZZQ'
]

const result = myArray
  .flat(Infinity)
  .reduce((r, s) => s.length > r.length ? s : r);
  
console.log(result);

answered Nov 11, 2018 at 5:38

Ori Drori

196k32 gold badges243 silver badges233 bronze badges

6 Comments

Adrian Brand Over a year ago

Problem with this method is that you are iterating the collection twice, it is quite inefficient. Not a real problem on a small data set but increases with the size of the input.

Ori Drori Over a year ago

This is a functional solution that splits the problem into two simple parts. Both parts are O(n), which translate to O(2n). In CS O(2n) is equivalent to O(n). This means that performance optimisation will be required only for huge arrays. In JS huge recursive solutions will fail most of the time (stack overflow).

Adrian Brand Over a year ago

You do realise that flat is a recursive function? developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…

Adrian Brand Over a year ago

And flat copies the array and consumes a huge amount of memory compared to a single reduce that only keeps a single string as an accumulator. The single reduce will only consume memory for the stack to the depth of the array nesting and will fail orders of magnitude later that flat.

Adrian Brand Over a year ago

When you say in CS O(2n) is equivalent to O(n), this may be true on the client side running in the browser where taking twice as long doesn't make much difference, but if it is on the server where you are servicing thousands of requesting per second it may be the difference between $500 a month in hosting costs vs $1,000 a month. That is not equivalent in my book.

|

Adrian Brand · Accepted Answer · 2018-11-11 05:52:08Z

1

You can do it with a single reduce

const myArray = [
  'ABC',
  'ABCD',
  'ABCDE', [
    'ABC',
    'ABCABABA', [
      'ABABABABABABABABAZZ'
    ],
    'ABCABABASS',

  ],
  'ABCDEFGH',
  'ABABABABZZQ'
];

const findLongestStr = array => array.reduce((result, item) => typeof item === 'string' ? item.length > result ? item : result : findLongestStr(item), '');
  
console.log(findLongestStr(myArray));

answered Nov 11, 2018 at 5:52

Adrian Brand

21.8k4 gold badges46 silver badges67 bronze badges

Comments

Mamun · Accepted Answer · 2018-11-11 05:59:23Z

1

You have to declare longestStr outside the function and also you have to use the return keyword

return longestString(item)

let myArray = [['ABC','ABCD','ABCDE',
    ['ABC','ABCABABA',
    ['ABABABABABABABABAZZ'],
    'ABCABABASS'],
   'ABCDEFGH',
   'ABABABABZZQ']]
   
let longestStr = ''
function longestString(arr) {
  arr.forEach(item => {
    if(typeof item === 'string') {
      if(item.length > longestStr.length) {
        longestStr = item;
        console.log('Longest Item', item);
      }    
      } else {
        return longestString(item)
      }
  });
  return longestStr;
}

console.log(longestString(myArray));

EDIT - You can pass longestStr as parameter to longestString function

let myArray = [['ABC','ABCD','ABCDE',
    ['ABC','ABCABABA',
    ['ABABABABABABABABAZZ'],
    'ABCABABASS'],
   'ABCDEFGH',
   'ABABABABZZQ']]

function longestString(arr,longestStr) {
  arr.forEach(item => {
    if(typeof item === 'string') {
      if(item.length > longestStr.length) {
        longestStr = item;
        console.log('Longest Item', item);
      }    
      } else {
        var value = longestString(item,longestStr);
        if(value.length > longestStr.length){
           longestStr = value;
        }
        return longestStr;
      }
  });
  return longestStr;
}

console.log(longestString(myArray,''));

edited Nov 11, 2018 at 5:59

answered Nov 11, 2018 at 5:40

Mamun

69k9 gold badges51 silver badges62 bronze badges

1 Comment

front_end_dev Over a year ago

You are maintaining the longestStr in the global context. We can passed as an argument to longestString itself.

front_end_dev · Accepted Answer · 2018-11-11 05:45:55Z

Recursively call the findLongestStr if the input is Array and maintain the current maximum value.

let myArray = [
    'ABC',
    'ABCD',
    'ABCDE',
    [
      'ABC',
      'ABCABABA',
      [
        'ABABABABABABABABAZZ'
      ],
    'ABCABABASS',

     ],
   'ABCDEFGH',
   'ABABABABZZQ'
   ];

function findLongestStr(input){
  return input.reduce(function(o,i){
     if(i.constructor === Array){
        var value = findLongestStr(i);
        console.log("value array => ",value);
        if(o.length < value.length){
          o = value;
        }
     }else{
           console.log("value i => ",i);
        if(o.length < i.length){
          o = i;
        }
     }
     return o;
  },"");
}

console.log("max length => ",findLongestStr(myArray));

Working jsFiddle demo - https://jsfiddle.net/k4yo35hb/1/

Mark · Accepted Answer · 2018-11-11 06:11:43Z

0

The main problem with you code is that you redefine longestStr each time the recursive function is called. Leaving you no way of comparing the longest string from each recursive call.

Using reduce() is a nice way to find the max of a regular un-nested array. You can add a little bit of recursion and still use reduce() for this which takes care of maintaining state between recursions because all the recursion unwinds within the reduce function:

let myArray = ['ABC','ABCD','ABCDE',['ABC','ABCABABA',['ABABABABABABABABAZZ'],'ABCABABASS',],'ABCDEFGH','ABABABABZZQ']


function longestString(arr) {
  return arr.reduce((longest, item) => {
    if (Array.isArray(item)) {
      let rec = longestString(item)
      if (rec.length > longest.length) longest = rec
    } else if (item.length > longest.length) longest = item;

    return longest
  }, '')
}

console.log(longestString(myArray))

edited Nov 11, 2018 at 6:11

answered Nov 11, 2018 at 5:56

Mark

92.7k8 gold badges116 silver badges156 bronze badges

2 Comments

front_end_dev Over a year ago

Without providing the default intial value in reduce function it's getting undefined in longest at first place.

Adrian Brand Over a year ago

If you don't define the initial accumulator in a reduce function it uses the first element of the array, not undefined. In this case you need to define the accumulator as an empty string just incase the first item is an array.

Nirit Levi · Accepted Answer · 2018-11-11 06:40:24Z

0

with respect to @Adrian Brand clean answer, here is the solution:

const findMaxStringInArray = (array, lastMax = '' ) => array.reduce((curMax,item)=>typeof item === 'string'?  item.length > curMax.length? item : curMax :  findMaxStringInArray(item, curMax) ,lastMax);

answered Nov 11, 2018 at 6:40

Nirit Levi

2611 silver badge7 bronze badges

Collectives™ on Stack Overflow

Find the longest string in a nested array using Recursion in Javascript?

7 Answers 7

Comments

6 Comments

Comments

1 Comment

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

Comments

6 Comments

Comments

1 Comment

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related