Leetcode #763 Partition Labels

public List<Integer> partitionLabels(String S) {
Map<Character, Integer> map = new HashMap<>();
// Store the last index of every character
for(int i = 0; i < S.length(); i++) {
char ch = S.charAt(i);
map.put(ch, i);
}
int max = 0;
List<Integer> result = new ArrayList<>();
int start = 0;
for(int i = 0; i < S.length(); i++) {
char ch = S.charAt(i);
int index = map.get(ch);
max = Math.max(index, max);
// we evaluate the maximum possible index of the current substring
if(max == i) {
int len = max - start + 1;
result.add(len);
start = i + 1;
}
}
return result;
}

--

--

--

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

An Introduction to Python Counter

Best Practices fo React Native App should Follow Every React Developers

Build and Deploy your free 20GB Oracle Autonomous Database with NodeJS 1/2

Explore React Fundamental Core Concept For Beginners

React App connect to AWS AppSync for Subscription

Why subscription is not working in Apollo client for AppSync

Too Green To Go

How to Create a Perfect Carousel Nav with React and Styled Component

How to install laravel browsershot in windows using xampp

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sweta Barman

Sweta Barman

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.

More from Medium

[Leetcode 525] Contiguous Array

543. Diameter of Binary Tree

[LeetCode] Problem Solving Pattern_Frequency Counter

Leetcode — Add Bold Tag in String