diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
index df0a040..8fa2481 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
@@ -81,7 +81,7 @@
                     notifyRemovedServiceToListeners(previousResponse, "Service record expired");
                 }
             };
-    private final ArrayMap<MdnsServiceBrowserListener, MdnsSearchOptions> listeners =
+    private final ArrayMap<MdnsServiceBrowserListener, ListenerInfo> listeners =
             new ArrayMap<>();
     private final boolean removeServiceAfterTtlExpires =
             MdnsConfigs.removeServiceAfterTtlExpires();
@@ -95,6 +95,32 @@
     private long currentSessionId = 0;
     private long lastSentTime;
 
+    private static class ListenerInfo {
+        @NonNull
+        final MdnsSearchOptions searchOptions;
+        final Set<String> discoveredServiceNames;
+
+        ListenerInfo(@NonNull MdnsSearchOptions searchOptions,
+                @Nullable ListenerInfo previousInfo) {
+            this.searchOptions = searchOptions;
+            this.discoveredServiceNames = previousInfo == null
+                    ? MdnsUtils.newSet() : previousInfo.discoveredServiceNames;
+        }
+
+        /**
+         * Set the given service name as discovered.
+         *
+         * @return true if the service name was not discovered before.
+         */
+        boolean setServiceDiscovered(@NonNull String serviceName) {
+            return discoveredServiceNames.add(MdnsUtils.toDnsLowerCase(serviceName));
+        }
+
+        void unsetServiceDiscovered(@NonNull String serviceName) {
+            discoveredServiceNames.remove(MdnsUtils.toDnsLowerCase(serviceName));
+        }
+    }
+
     private class QueryTaskHandler extends Handler {
         QueryTaskHandler(Looper looper) {
             super(looper);
@@ -311,12 +337,16 @@
         ensureRunningOnHandlerThread(handler);
         this.searchOptions = searchOptions;
         boolean hadReply = false;
-        if (listeners.put(listener, searchOptions) == null) {
+        final ListenerInfo existingInfo = listeners.get(listener);
+        final ListenerInfo listenerInfo = new ListenerInfo(searchOptions, existingInfo);
+        listeners.put(listener, listenerInfo);
+        if (existingInfo == null) {
             for (MdnsResponse existingResponse : serviceCache.getCachedServices(cacheKey)) {
                 if (!responseMatchesOptions(existingResponse, searchOptions)) continue;
                 final MdnsServiceInfo info =
                         buildMdnsServiceInfoFromResponse(existingResponse, serviceTypeLabels);
                 listener.onServiceNameDiscovered(info, true /* isServiceFromCache */);
+                listenerInfo.setServiceDiscovered(info.getServiceInstanceName());
                 if (existingResponse.isComplete()) {
                     listener.onServiceFound(info, true /* isServiceFromCache */);
                     hadReply = true;
@@ -480,9 +510,10 @@
     private void notifyRemovedServiceToListeners(@NonNull MdnsResponse response,
             @NonNull String message) {
         for (int i = 0; i < listeners.size(); i++) {
-            if (!responseMatchesOptions(response, listeners.valueAt(i))) continue;
+            if (!responseMatchesOptions(response, listeners.valueAt(i).searchOptions)) continue;
             final MdnsServiceBrowserListener listener = listeners.keyAt(i);
             if (response.getServiceInstanceName() != null) {
+                listeners.valueAt(i).unsetServiceDiscovered(response.getServiceInstanceName());
                 final MdnsServiceInfo serviceInfo = buildMdnsServiceInfoFromResponse(
                         response, serviceTypeLabels);
                 if (response.isComplete()) {
@@ -511,10 +542,9 @@
         final MdnsResponse currentResponse =
                 serviceCache.getCachedService(serviceInstanceName, cacheKey);
 
-        boolean newServiceFound = false;
+        final boolean newInCache = currentResponse == null;
         boolean serviceBecomesComplete = false;
-        if (currentResponse == null) {
-            newServiceFound = true;
+        if (newInCache) {
             if (serviceInstanceName != null) {
                 serviceCache.addOrUpdateService(cacheKey, response);
             }
@@ -525,25 +555,28 @@
             serviceBecomesComplete = !before && after;
         }
         sharedLog.i(String.format(
-                "Handling response from service: %s, newServiceFound: %b, serviceBecomesComplete:"
+                "Handling response from service: %s, newInCache: %b, serviceBecomesComplete:"
                         + " %b, responseIsComplete: %b",
-                serviceInstanceName, newServiceFound, serviceBecomesComplete,
+                serviceInstanceName, newInCache, serviceBecomesComplete,
                 response.isComplete()));
         MdnsServiceInfo serviceInfo =
                 buildMdnsServiceInfoFromResponse(response, serviceTypeLabels);
 
         for (int i = 0; i < listeners.size(); i++) {
-            if (!responseMatchesOptions(response, listeners.valueAt(i))) continue;
+            // If a service stops matching the options (currently can only happen if it loses a
+            // subtype), service lost callbacks should also be sent; this is not done today as
+            // only expiration of SRV records is used, not PTR records used for subtypes, so
+            // services never lose PTR record subtypes.
+            if (!responseMatchesOptions(response, listeners.valueAt(i).searchOptions)) continue;
             final MdnsServiceBrowserListener listener = listeners.keyAt(i);
+            final ListenerInfo listenerInfo = listeners.valueAt(i);
+            final boolean newServiceFound = listenerInfo.setServiceDiscovered(serviceInstanceName);
             if (newServiceFound) {
                 sharedLog.log("onServiceNameDiscovered: " + serviceInfo);
                 listener.onServiceNameDiscovered(serviceInfo, false /* isServiceFromCache */);
             }
 
             if (response.isComplete()) {
-                // There is a bug here: the newServiceFound is global right now. The state needs
-                // to be per listener because of the  responseMatchesOptions() filter.
-                // Otherwise, it won't handle the subType update properly.
                 if (newServiceFound || serviceBecomesComplete) {
                     sharedLog.log("onServiceFound: " + serviceInfo);
                     listener.onServiceFound(serviceInfo, false /* isServiceFromCache */);
@@ -579,7 +612,7 @@
     private List<MdnsResponse> makeResponsesForResolve(@NonNull SocketKey socketKey) {
         final List<MdnsResponse> resolveResponses = new ArrayList<>();
         for (int i = 0; i < listeners.size(); i++) {
-            final String resolveName = listeners.valueAt(i).getResolveInstanceName();
+            final String resolveName = listeners.valueAt(i).searchOptions.getResolveInstanceName();
             if (resolveName == null) {
                 continue;
             }
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
index 7a2e4bf..0572e7b 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
@@ -1492,6 +1492,91 @@
     }
 
     @Test
+    public void testProcessResponse_SubtypeChange() {
+        client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
+                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                serviceCache);
+
+        final String matchingInstance = "instance1";
+        final String subtype = "_subtype";
+        final String ipV4Address = "192.0.2.0";
+        final String ipV6Address = "2001:db8::";
+
+        final MdnsSearchOptions options = MdnsSearchOptions.newBuilder()
+                .addSubtype("othersub").build();
+
+        startSendAndReceive(mockListenerOne, options);
+
+        // Complete response from instanceName
+        final MdnsPacket packetWithoutSubtype = createResponse(
+                matchingInstance, ipV4Address, 5353, SERVICE_TYPE_LABELS,
+                Collections.emptyMap() /* textAttributes */, TEST_TTL);
+        final MdnsPointerRecord originalPtr = (MdnsPointerRecord) CollectionUtils.findFirst(
+                packetWithoutSubtype.answers, r -> r instanceof MdnsPointerRecord);
+
+        // Add a subtype PTR record
+        final ArrayList<MdnsRecord> newAnswers = new ArrayList<>(packetWithoutSubtype.answers);
+        newAnswers.add(new MdnsPointerRecord(
+                // PTR should be _subtype._sub._type._tcp.local -> instance1._type._tcp.local
+                Stream.concat(Stream.of(subtype, "_sub"), Arrays.stream(SERVICE_TYPE_LABELS))
+                        .toArray(String[]::new),
+                originalPtr.getReceiptTime(), originalPtr.getCacheFlush(), originalPtr.getTtl(),
+                originalPtr.getPointer()));
+        processResponse(new MdnsPacket(
+                packetWithoutSubtype.flags,
+                packetWithoutSubtype.questions,
+                newAnswers,
+                packetWithoutSubtype.authorityRecords,
+                packetWithoutSubtype.additionalRecords), socketKey);
+
+        // The subtype does not match
+        final InOrder inOrder = inOrder(mockListenerOne);
+        inOrder.verify(mockListenerOne, never()).onServiceNameDiscovered(any(), anyBoolean());
+
+        // Add another matching subtype
+        newAnswers.add(new MdnsPointerRecord(
+                // PTR should be _subtype._sub._type._tcp.local -> instance1._type._tcp.local
+                Stream.concat(Stream.of("_othersub", "_sub"), Arrays.stream(SERVICE_TYPE_LABELS))
+                        .toArray(String[]::new),
+                originalPtr.getReceiptTime(), originalPtr.getCacheFlush(), originalPtr.getTtl(),
+                originalPtr.getPointer()));
+        processResponse(new MdnsPacket(
+                packetWithoutSubtype.flags,
+                packetWithoutSubtype.questions,
+                newAnswers,
+                packetWithoutSubtype.authorityRecords,
+                packetWithoutSubtype.additionalRecords), socketKey);
+
+        final ArgumentMatcher<MdnsServiceInfo> subtypeInstanceMatcher = info ->
+                info.getServiceInstanceName().equals(matchingInstance)
+                        && info.getSubtypes().equals(List.of("_subtype", "_othersub"));
+
+        // Service found callbacks are sent now
+        inOrder.verify(mockListenerOne).onServiceNameDiscovered(
+                argThat(subtypeInstanceMatcher), eq(false) /* isServiceFromCache */);
+        inOrder.verify(mockListenerOne).onServiceFound(
+                argThat(subtypeInstanceMatcher), eq(false) /* isServiceFromCache */);
+
+        // Address update: update callbacks are sent
+        processResponse(createResponse(
+                matchingInstance, ipV6Address, 5353, SERVICE_TYPE_LABELS,
+                Collections.emptyMap(), TEST_TTL), socketKey);
+
+        inOrder.verify(mockListenerOne).onServiceUpdated(argThat(info ->
+                subtypeInstanceMatcher.matches(info)
+                        && info.getIpv4Addresses().equals(List.of(ipV4Address))
+                        && info.getIpv6Addresses().equals(List.of(ipV6Address))));
+
+        // Goodbye: service removed callbacks are sent
+        processResponse(createResponse(
+                matchingInstance, ipV6Address, 5353, SERVICE_TYPE_LABELS,
+                Collections.emptyMap(), 0L /* ttl */), socketKey);
+
+        inOrder.verify(mockListenerOne).onServiceRemoved(matchServiceName(matchingInstance));
+        inOrder.verify(mockListenerOne).onServiceNameRemoved(matchServiceName(matchingInstance));
+    }
+
+    @Test
     public void testNotifySocketDestroyed() throws Exception {
         client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
                 mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,