[go: up one dir, main page]
Scribd
Upload
11 views4 pages

Ap3 1

The document demonstrates the concept of greedy algorithms by solving two problems - removing duplicate letters from a string and dividing an array into three equal parts. Program 1 removes duplicate letters from a string in lexicographical order. Program 2 divides a binary array into three parts with equal number of 1s. The learning outcomes are implementing greedy methods, properties of greedy algorithms, and applying greedy methods to problems.

Uploaded by

eyboss0099
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views4 pages

Ap3 1

The document demonstrates the concept of greedy algorithms by solving two problems - removing duplicate letters from a string and dividing an array into three equal parts. Program 1 removes duplicate letters from a string in lexicographical order. Program 2 divides a binary array into three parts with equal number of 1s. The learning outcomes are implementing greedy methods, properties of greedy algorithms, and applying greedy methods to problems.

Uploaded by

eyboss0099
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiment 3.1

Name: Nikita UID: 21BCS2785


Branch: BE-CSE Section/Group: 21BCS-FL-603-B
Semester: 6 Date of Performance: 15-03-2024
Subject Name: AP Lab - II Subject Code: 21CSP-351

1.Aim: To demonstrate the concept of Greedy.


2.Objective:
1. Remove Duplicate Letters:
Problem statement- Given a string s, remove duplicate letters so that every letter appears once and only once.
You must make sure your result is the smallest in lexicographical order among all possible results.
Example: Input: s=”bcabc”
Output:”abc”

2.Three Equal Parts


Problem statement- Problem statement- You are given an array arr which consists of only zeros and ones,
divide the array into three non-empty parts such that all of these parts represent the same binary value.If it is
possible, return any [i, j] with i + 1 < j, such that: arr[0], arr[1], ..., arr[i] is the first part,

3.Script and Output:

Program 1: Remove Duplicate Letters


class Solution {
public:
string removeDuplicateLetters(string s) {
string ans;
vector<int> count(128);
vector<bool> used(128);

for (const char c : s)


++count[c];

for (const char c : s) {


--count[c];
if (used[c])
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

continue;
while (!ans.empty() && ans.back() > c &&
count[ans.back()] > 0) {
used[ans.back()] = false;
ans.pop_back();
}
used[c] = true;
ans.push_back(c);
}

return ans;
}
};
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Program 2: Three Equal Parts


class Solution {
public:
vector<int> threeEqualParts(vector<int>& arr) {
const int ones = ranges::count_if(arr, [](int a) { return a
== 1; });
if (ones == 0)
return {0, static_cast<int>(arr.size()) - 1};
if (ones % 3 != 0)
return {-1, -1};
int k = ones / 3;
int i;
int j;
int first;
int second;
int third;
for (i = 0; i < arr.size(); ++i)
if (arr[i] == 1) {
first = i;
break;
}
int gapOnes = k;
for (j = i + 1; j < arr.size(); ++j)
if (arr[j] == 1 && --gapOnes == 0) {
second = j;
break;
}
gapOnes = k;
for (i = j + 1; i < arr.size(); ++i)
if (arr[i] == 1 && --gapOnes == 0) {
third = i;
break;
}
while (third < arr.size() && arr[first] == arr[second] &&
arr[second] == arr[third]) {
++first;
++second;
++third;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

}
if (third == arr.size())
return {first - 1, second};
return {-1, -1};
}
};

4.Learning Outcomes:
1. Implementing greedy method.
2. Learnt about the properties of greedy algos.
3. Learnt about usage of greedy method at various places.
4. Demonstrate the use of greedy method through problems.

You might also like