Finding largest number in a string using Dart with O(n) Complexity

Finding largest number in a string using Dart with O(n) Complexity

Problem Statement

You are given a string that has lowercase letters and numbers. Your task is to compare the number groupings and return the largest number. Numbers will not have leading zeros.

For example, solve("gh12cdy695m1") = 695, because this is the largest of all number groupings.

Test cases

import "package:test/test.dart";
import "package:solution/solution.dart";

void main() {
  group("Fixed tests", () {
    test("Testing for gh12cdy695m1", () => expect(solve('gh12cdy695m1'), equals(695)));
    test("Testing for 2ti9iei7qhr5", () => expect(solve('2ti9iei7qhr5'), equals(9)));
    test("Testing for vih61w8oohj5", () => expect(solve('vih61w8oohj5'), equals(61)));
    test("Testing for f7g42g16hcu5", () => expect(solve('f7g42g16hcu5'), equals(42)));
    test("Testing for lu1j8qbbb85", () => expect(solve('lu1j8qbbb85'), equals(85)));

My Approach

int solve(String s) {
  final pattern = RegExp(r'[0-9]+');
  final matches = pattern.allMatches(s);
  final numbers = => int.parse(!)).toList();
  final largestNumber = numbers.reduce((current, next) => current > next ? current : next);
  return largestNumber;

Regex expressions are ways to specify match-checking algorithm for input texts. It allows us to match, or accept input texts.

The allMatches method is used to find all the substrings in the given string that match the defined pattern.

The matched substrings are mapped to their integer representation to form a list of numbers.

The reduce method is employed to iterate through a list of numbers and determine the largest number.

The complexity for regular expression matching is O(n), for mapping matches to integers is O(m), and to find the largest number is O(m).


n is the length of string, and m is the number of matches.

Overall time complexity is O(n).

Wrapping Up

There you go! Let me know what better approach you have to solving the above problems. ;)

Problem statement source: Codewars

references to achieve solution:

allMatches method - RegExp class - dart:core library - Dart APIAPI docs for the allMatches method from the RegExp class, for the Dart programming language.api.flutter.devWhat are regular expressions, and why should you use them?Regular expressions (regex) are a way to describe patterns in string data. It is essentially a sequence of characters…

About Me

I am Zaahra, a Google Women Techmakers Ambassador who enjoy mentoring people and writing about technical contents that might help people in their developer journey. I also enjoy building stuffs to solve real life problems.

To reach me:


X (previously Twitter): _fz3hra



Umme Faatimah-Iz-Zaahra Mujore | Google Women TechMakers Ambassador | Software Engineer